每个节点  tree[i]=a[i-2^k+1]+....+a[i]

k为取最低位的1；

转变为二进制 

　　例如 7:    tree 0111 = a 0111 

　　　　 8:    tree 1000 = a 0001 + a 0010 + a 0011 +...+ a 1000;

取最低位的1

int lowbit(int x){    return x&(-x);}

修改：

void add(int x,int k){    while(x<=n)    {        tree[x]+=k;        x+=lowbit(x);    }}/**

  7(111)          ans+=C[7]

lowbit(7)=001  7-lowbit(7)=6(110)    ans+=C[6]

lowbit(6)=010  6-lowbit(6)=4(100)    ans+=C[4]

lowbit(4)=100  4-lowbit(4)=0(000)    

*//

查询（区间查询类似前缀和）：

int query(int x){    int ans=0;    while(x>0)    {        ans+=tree[x];        x-=lowbit(x);    }    return ans;}

 

差分：

对于 a 1 5 6 2 4  5 

a[i]-a[i-1] 得到 b 1 4 1 -4 2 1

可得 a[i]=b[1]+...+b[i];

此时a 2-4 全部加上 2 

a 1 7 8 4 4 5

b 1 6 1 -4  0 5

只有2 4 对应的只改变 2 +k 4 -k;

只需要对应修改 2 4 的值

 

洛谷3368：

#include
     
      using namespace std;const int maxn=5e5+10;#define ll long longint tree[maxn];int lowbit(int x){    return x&(-x);}int n,m;void add(int x,int k){    while(x<=n)    {        tree[x]+=k;        x+=lowbit(x);    }}int query(int x){    int ans=0;    while(x>0)    {        ans+=tree[x];        x-=lowbit(x);    }    return ans;}signed main(){    int a,b;    scanf("%d%d%d",&n,&m,&b);    add(1,b);    for(int i=2;i<=n;i++)    {        scanf("%d",&a);        add(i,a-b);        b=a;    }    for(int i=1;i<=m;i++)    {        int cmd,x,y,pos;        scanf("%d",&cmd);        if(cmd==1)        {            scanf("%d%d%d",&x,&y,&pos);            add(x,pos);            add(y+1,-pos);        }        if(cmd==2)        {            scanf("%d",&pos);            //cout<
      
       <<" "<
       
        <