前往：我自己搭建的博客
题目
洛谷P3368树状数组2
题解
将普通树状数组操作和差分思想结合，就可以实现区间修改和单点查询。若对区间[l,r]进行修改，则在l处修改，并在r+1处反向修改。在查询时，询问x处的值，则求[1,x]的和，若x在[l,r]内，则会累加l处的修改，若x在r右侧，则r+1处的反向修改会抵消l处的修改。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,m;
int sum[maxn],a[maxn]; //a[]存初始数据
inline int lowbit(int x) {return x&(-x);}
inline void add(int x,int y) {for( ;x<=n;x+=lowbit(x)) sum[x]+=y;}
inline int ask(int x) {int ans=0; for( ;x;x-=lowbit(x)) ans+=sum[x]; return ans;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int t; scanf("%d",&t);
if(t==1)
{
int x,y,k; scanf("%d%d%d",&x,&y,&k);
add(x,k); add(y+1,-k);
}
else
{
int x; scanf("%d",&x);
printf("%d\n",a[x]+ask(x)); //注意加上原始数据
}
}
return 0;
}
