AcWing243. 一个简单的整数问题2(树状数组实现区间修改+区间查询)
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
代码
#include <iostream> using namespace std; typedef long long LL; const int N = 100010; int n , m; int a[N]; LL tr1[N] , tr2[N]; int lowbit(int x) { return x & -x; } void add(LL tr[] , int x , LL c) { for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c; } LL sum(LL tr[] , int x) { LL res = 0; for(int i = x ; i ; i -= lowbit(i)) res += tr[i]; return res; } LL prefix_sum(int x) { return sum(tr1 , x) * (x + 1) - sum(tr2 , x); } int main() { scanf("%d%d" , &n , &m); for(int i = 1; i <= n ; i++) scanf("%d", &a[i]); for(int i = 1 ; i <= n ; i++) { int b = a[i] - a[i - 1]; add(tr1 , i , b); add(tr2 , i , (LL)b * i); } while(m--) { int l , r , d; char op[2]; scanf("%s%d%d" , op , &l , &r); if(*op == 'Q') cout << prefix_sum(r) - prefix_sum(l - 1) << endl; else { scanf("%d" , &d); add(tr1 , l , d) , add(tr1 , r + 1 , -d); add(tr2 , l , l * d) , add(tr2 , r + 1 , (r + 1) * (- d)); } } return 0; }
