前缀和与差分
1.一维前缀和
注意
<ol> 前缀和下标要从1开始，因为边界S0要定义成0。
作用：可以快速求出某个数组区间内的和。
[code]#includeusing namespace std;const int N = 1e5 + 10;int s[N],a[N];//全局变量默认为0int main(){ int m,n; cin>>n>>m; for(int i=1;i>a; for(int i=1;i>l>>r; coutm>>q; for(int i=1;ia[j]; for(int i=1;i x1 >> y1 >> x2 >> y2; coutm; for(int i=1;i>a; insert(i,i,a);//重点理解==》差分（上面提到的加值操作） } while(m--) { int l,r,c; cin>>l>>r>>c; insert(l,r,c); } for(int i=1;i=1;i--) for(int j=m;j>=1;j--) a[j] = a[j] - a[i-1][j] - a[j-1] + a[i-1][j-1];//方法一求差分数组（只需要开一个数组） while(q--) { int x1,y1,x2,y2,c; cin>>x1>>y1>>x2>>y2>>c; insert(x1,y1,x2,y2,c); } for(int i=1;i |
