树状数组
一般求解带修改的区间查询。比如带修改的区间和问题。
lowbit
lowbit(x) 二进制下x最低位的１所对应的数,返回的是(2^k)。
比如8(1000)返回8，7(0111) 返回1。
比如说要更新2这个点,首先2更新,然后2+lowbit(2)=4更新,然后4+lowbit(4)=8更新...
更新7这个点,首先7更新,然后7+lowbit(7)=8更新...
比如说要查询1-2的区间和,首先返回2的值,然后2-lowbit(2) = 0结束
比如要查询1-7的区间和,首先返回7的值,然后7-lowbit(7) = 6,然后6-lowbit(6) = 4,然后4-lowbit(4)=0结束
单点更新,区间查询
int a[maxn],t[maxn]; //原数组,树状数组
int lowbit(int x)
{
return x&(-x);
}
void updata(int i,int k) //在i的位置上加k
{
while (i <= n)
{
t[i] += k;
i += lowbit(i);
}
}
int getsum(int i) //求1-i区间的和
{
int res = 0;
while (i > 0)
{
res += t[i];
i -= lowbit(i);
}
return res;
}
区间更新,单点查询
利用差分建树,1-i区间的的和就是i的值(A[i] = sum_{j=1}^i D[j])
[x,y]区间内加上k,因为是单点查询,只要求i的时候加到了k,就是正确的
updata(x,k); //加上k
updata(y+1,-k); //之后的减去k
区间更新,区间查询
i的前n项和(sum_{i=1}^n A[i] = sum_{i=1}^n sum_{j=1}^i D[j])
(= n * D[1] + (n-1) * D[2] + (n-2) * D[3] + cdots + D[i])
(= n * A[n] - (0 * D[1] + 1 * D[2] + 2 * D[3] + cdots + (n-1) * D[n]))
所以(sum_{i=1}^n A[i] = n * sum_{i=1}^n D[i] - sum_{i=1}^{n} (D[i] * (i-1)))
sum1[i] = D[i]，sum2[i] = D[i]*(i-1);
int a[maxn],sum1[maxn],sum2[maxn];
int lowbit(int x){
return x&(-x);
}
void updata(int i,int k){
int x = i; //因为x不变，所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
int getsum(int i){ //求前缀和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}