给定一个长度为 (n) 的数组，(q) 组操作：
-
将某一个数加上 (x)
-
求出某区间每一个数的和
显然，假设你现在什么也不会。
我们只考虑第 (2) 个操作，即先不考虑修改，如何处理区间和的询问？
显然，对于初始的数组 (a_i)，只需要做一个前缀和 (s) 使得：
[s_j = sum_{i=1}^j a_i
]
这样，对于一组询问：
[sum_{i=l}^r a_i = s_r - s_{l-1}
]
可以做到 (mathcal{O}(n) - mathcal{O}(1)).
但是现在出题人加入了修改操作，你再修改的时候不得不把 (s) 重推一遍。
这样 (mathcal{O}(n) - mathcal{O}(n)) 我们就完了啊。
从前缀和上我们可以考虑，如何用 较少的前缀和记录较多的区间答案。
一个合法的思路是利用 ( ext{RMQ})，记：
[f_{x,y} = sum_{i=x}^{min(x+2^y-1 , n)} a_i
]
然后可以做到 (mathcal{O}(n log n) - mathcal{O}(1)).
但是我们觉得这不好，我们用部分前缀和。
即我们只记录一部分的前缀和，查询时查询较少一部分，修改时也只要修改较少一部分，达到复杂度的均衡。
因此，我们想到了用 ( ext{lowbit}) 表示前缀的长度。你可以理解为每次 (+) 或 (-) 一个 ( ext{lowbit}) 会在原数的二进制中砍掉一位。
这样，我们就可以做到 (mathcal{O}(n log n) - mathcal{O}(log n)).
这就是树状数组。其实树状数组的本质就是用 部分前缀和维护差分数组。
时间复杂度：(mathcal{O}(n log n) - mathcal{O}(log n)).
实际得分：(100pts)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int a[N]; ll c[N];
int n,m,x,y;
inline int lowbit(int x) {
//求2^{x末尾0的个数}
return x & (-x);
}
inline ll sum(int x) {
//求n的前缀和
ll s=0; while(x>0) {
s+=c[x];
x-=lowbit(x);
//这是x节点紧贴着的前一个区间
} return s;
}
inline void update(int x,int k) {
a[x]+=k; while(x<=n) {
c[x]+=k; //暴力加和
x+=lowbit(x);
//这是x节点紧贴着的后一个区间
}
}
int main(){
n=read(); m=read();
for(int i=1;i<=n;i++) {
x=read(); update(i,x);
} while(m--) {
int opt=read(); x=read(),y=read();
if(opt==1) update(x,y);
else printf("%lld
",sum(y)-sum(x-1));
}
return 0;
}