poj3468 A Simple Problem with Integers（用线段树和树状数组实现）

原题链接：A Simple Problem with Integers

题意：给定一个数列A[1],A[2]...A[N]以及Q个操作，按顺序行这些操作,操作分为两种： 1、给出l,r,x 对A[l],A[l+1]...A[r]同时加上x 2、给出l,r     求A[l]+A[l+1]+...+A[r]的值 Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15 /* 用树状数组实现，复杂度是Q*lg(N) 对区间[l,r]同时加上x：令s(i)为加x之前的和，s'(i)为加x之后的和 1. i<l s'(i) = s(i) 2. l<=i<=r s'(i) = s(i) + x*(i-l+1) = s(i) + x*i-x*(l-1) 3. r<i s'(i) = s(i) + x*(r-l+1) sum(bit, i)代表树状数组bit的前i项和 加上x之后的前i项和s'(i) = sum(bit1,i)*i + sum(bit0,i); 在间[l,r]同时加上x需要以下4步(此操作保证l<i<r时s'(i)的增量是(i-l+1)*x,同时不应想次区间前后的值)： 1、在bit0的l位置上加上-x(l-1) 2、在bit0的r+1位置上加上rx 3、在bit2的l位置上加上x 4、在bit2的r+1位置上加上-x 若求[l,r]内的和，即是s'(r)-s'(l-1) */ #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100001; const int MAX_Q = 100001; typedef long long ll; //输入数据 int N, Q; int A[MAX_N]; char T[MAX_Q]; int L[MAX_Q], R[MAX_Q], X[MAX_Q]; //BIT树状数组 ll bit0[MAX_N + 1], bit1[MAX_N + 1]; ll sum(ll *b, int i){ //sum(bit, i)是树状数组bit的前i项和 ll s = 0; while(i > 0){ s += b[i]; i -= i & -i; } return s; } void add(ll *b, int i, int v){ //i位置上加v while(i <= N){ b[i] += v; i += i & -i; } } void solve(){ for(int i = 1;i <= N;i ++){ add(bit0, i, A[i]); } for(int i = 1;i <= Q;i ++){ if(T[i] == 'C'){ add(bit0, L[i], -X[i] * (L[i] - 1)); add(bit1, L[i], X[i]); add(bit0, R[i] + 1, X[i] * R[i]); add(bit1, R[i] + 1, -X[i]); }else{ ll res = 0; res += sum(bit0, R[i]) + sum(bit1, R[i]) * R[i]; res -= sum(bit0, L[i] - 1) + sum(bit1, L[i] - 1) * (L[i] - 1); printf("%lld\n", res); } } } int main(){ scanf("%d%d", &N, &Q); for(int i = 1;i <= N;i ++) scanf("%d", &A[i]); for(int i = 1;i <= Q;i ++){ scanf(" %c", &T[i]); if(T[i] == 'C') scanf("%d%d%d", &L[i], &R[i], &X[i]); else scanf("%d%d", &L[i], &R[i]); } solve(); return 0; }

//用线段树实现,复杂度Q*lgN #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int MAX_N = 100001; const int MAX_Q = 100001; const int DAT_SIZE = (1 << 18) - 1; //输入数据 int N, Q; int A[MAX_N]; char T[MAX_Q]; int L[MAX_Q], R[MAX_Q], X[MAX_Q]; //线段树 ll data[DAT_SIZE]; //data[i]:第i个节点对应的区间的所有元素共同加上的值 ll datb[DAT_SIZE]; //datb[i]:第i个节点对应的区间除去data[i]之外的其他值得和 //对区间[a,b)同时加x，k是节点的编号，对应的区间[l,r) void add(int a, int b, int x, int k, int l, int r){ if(a <= l && b >= r){ //[a,b)包含[l,r) data[k] += x; }else if(l < b && r > a){ // [a,b)与[l,r)有交集(l<a<r<b || l<a<b<r || a<l<b<r) datb[k] += (min(b, r) - max(a, l)) * x; //保存交集区间的和 add(a, b, x, k * 2 + 1, l, (l + r) / 2); //左孩子 add(a, b, x, k * 2 + 2, (l + r) / 2, r); //右孩子 } } //计算[a,b)的和，k是节点的编号，对应的区间是[l,r) ll sum(int a, int b, int k, int l, int r){ if(b <= l || r <= a){ //没有交集 return 0; }if(a <= l && r <= b){ //[a,b)包含[l,r) return data[k] * (r - l) + datb[k]; //节点保存的和 }else{ //(b > l && r > a) ll res = (min(b, r) - max(a, l)) * data[k]; int mid = (l + r) / 2; res += sum(a, b, k * 2 + 1, l, mid); res += sum(a, b, k * 2 + 2, mid, r); return res; } } void solve(){ for(int i = 0;i < N;i ++){ //起点从0开始 add(i, i + 1, A[i], 0, 0, N); } for(int i = 0;i < Q;i ++){ if(T[i] == 'C'){ add(L[i] - 1, R[i], X[i], 0, 0, N); //加 }else { printf("%lld\n", sum(L[i] - 1, R[i], 0, 0, N)); //求和 } } } int main(){ scanf("%d%d", &N, &Q); for(int i = 0;i < N;i ++) scanf("%d", &A[i]); for(int i = 0;i < Q;i ++){ scanf(" %c", &T[i]); if(T[i] == 'C') scanf("%d%d%d", &L[i], &R[i], &X[i]); else scanf("%d%d", &L[i], &R[i]); } solve(); return 0; }