void lowbit(int x){return x&(-x);} void update(int x,int k){ for(int i=x;i<=n;i+=lowbit(i)){ tree[i]+=k; } } int getsum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)){ sum+=tree[i]; } return sum; }
给定区间[x,y]求其中的每个数的和
sum=getsum(y)-getsum(x-1);
给定区间[x,y]使其中各个数加上k
运用到差分思想：令 b[i] = a[i] - a[i-1] 其中 a[0] = 0; 易证得 a[i] = b[1] + b[2] + b[3] + ... + b[i]
eg：如果 a[5] = {5, 6, 3, 8, 12} 则 b[5] = {5, 1, -3, 5, 4}，若在区间[2,4]中每个数都分别加上2得：a[5] = {7, 8, 5, 10, 14} 则 b[5] = {7, 1, -3, 5, 2}
观察可知，若要使得[x,y]中每个数加上k，只需在b[x]上加k，b[y+1]减k即可完成区间加的操作。
int a,now=0; //now=a[i-1] for(int i=1;i<=n;++i){ scanf("%d",&a); update(i,a-now); now=a; //更新 } update(x,k); update(y+1,-k);
在数组x的位置加上k
update(x,k);
求数组x位置上的值为多少
常规版：
getsum(x)-getsum(x-1)
差分版：
getsum(x);
原文：https://www.cnblogs.com/-Joker/p/10841656.html