ZhYic

题解 P3368 【【模板】树状数组 2】



2017-12-23 16:13:22
首发于ZhYic的洛谷博客


就是常规写法


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 230000
int t[N<<2],n,op,l,r,type,x;
inline int lowbit(int &x){return x&(-x);}//可以不写成函数
int getsum(int x)//求指定区间和
{
	int sum=0;
	while(x>0)
	{
	    sum+=t[x];
	    x-=lowbit(x);
	}
	return sum;
}
void update(int x,int dlt)//树状数组更新(加一个值)
{
	while(x<=n)
	{
	    t[x]+=dlt;
	    x+=lowbit(x);
	}
}
int main()
{
	ios::sync_with_stdio(false);//cin,cout优化;
	cin>>n>>op;
	for(int i=1;i<=n;i++)
	{
	    cin>>x;
	    update(i,x);//初值为0,直接加就是赋了值
	}
	while(op--)
	{
	    cin>>type>>l>>r;
	    if(type==2)printf("%d\n",getsum(r)-getsum(l-1));//前缀和思想,1~l - 1~(l-1)
	    else update(l,r);
	}
}
	
解释如下:

来源:百度图片搜索

树状数组每个节点所存的值都有不同含义,具体意义则为C[i]=A[i]+A[i-1]+....+A[i-2^k+1](k表示i的二进制末尾连续0的个数);

举个粟子

C[1]=a[1];
	C[2]=a[2]+a[1];
	C[3]=a[3];(3='11'[2],所以k=0,i-2^k+1=3-1+1=3)
	C[4]=a[4]+a[3]+a[2]+a[1];(4='100',k=2,i-2^k+1=4-2^2+1=1)

依此类推。 而如何得到一个数二进制末尾0的个数呢?这就需要用到补码(戳这里)了,具体解释见此完全认识树状数组

易知(假的,二进制数A在第k位有个1且最低位不为1,则表示的是第1~k位有1,且小于A的C[ ]的和。

如:3=11,C3=C'11';4=100,C4=C'001'+C'010'+C'011'+C'100';

最后,一定要记住:看不懂也不要紧,会用就可以。

微笑