树状数组简介

树状数组
c[1]:=a[1];
c[2]:=a[1]+a[2];
c[3]:=a[3];
c[4]:=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4];
c[5]:=a[5];
c[6]:=a[5]+a[6];
c[7]:=a[7];
c[8]:=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]=c[4]+c[6]+c[7]+a[8];
维护前缀和
已知a[i]
c(i,j)为修改 a[i]:=j;相当于：u:=a[i];a[i]:=u+(j-u);设t=j-u;
询问q(i) s(i)=(a[1]+a[2]+……a[i]);
c[i]:=a[i-2^k+1]+a[i-2^k+2]+...+a[i];
k为i在二进制形式下末尾0的个数
起点是把i的最后一个1变为0再加一
x=76=64+8+4=(1001100)(2);
-x是二进制码=x的二进制码取反+1
-76=(0110011+1)(2)=(0110100)(2)
k=2
76 and -76=(100)(2)
2^k=x and(-x){and相同取1,不同取0}
lowbit(x):=x and(-x);
lowbit(x)=x and (x xor(x-1)){xor 异或0取反,异或1不变}
x xor (x-1)=-x
si:=a1+a2+...+ai=ci+a1+a2+...+a(i-2^k)=ci+si(i-2^k)=ci+c(i-2^k)+s(i-2^k-lowbit(i-2^k))
lowbit(7)=1(2^0)
lowbit(6)=2(2^1)
lowbie(4)=4(2^2)
s7=c7+s6=c7+c6+c4=c7+c6+c4+s0=c7+c6+c4