目录

1 题意2 思路2.1 时间复杂度分析2.2 实现

---

1 题意

  给定$n$个数，再给出$m$个询问，每个询问给出区间$[l_i,r_i]$和$x$，要求你在$[l_i,r_i]$上的每一个值都加上$x$，最后询问区间$[l,r]$的区间和。

2 思路

  由于更新和查询是分开的，所以可以用打标记的方式更新。   如果要将区间$[l_i,r_i]$加上$x$，那么可以令$b[l_i]+=x,b[r_i+1]-=x$。   最后累加上$b[i]$，即可得到每个数需要加上的值。

2.1 时间复杂度分析

  由于修改和询问的时间复杂度都是$\mathcal{O}(1)$，所以总的时间复杂度为$\mathcal{O}(n+m)$。

2.2 实现

#include<iostream> #include<cstdio> using namespace std; const int N=1e3+10; int a[N],b[N]; int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(m--){ int l,r,x;scanf("%d %d %d",&l,&r,&x); b[l]+=x;b[r+1]-=x; } for(int i=1;i<=n;i++) b[i]+=b[i-1],a[i]+=b[i],a[i]+=a[i-1]; int l,r;scanf("%d %d",&l,&r); printf("%d\n",a[r]-a[l-1]); return 0; }