浅析树状数组+模版题 luogu P3374+模版题 luogu P3368

功能

维护区间[1,r]的数字和

实现

• lowbit（x）：返回x在二进制下的最后一位一的十进制
  如：
  lowbit（01001100）=00000100

#define lowbit(x) (x&(-x))

我只能说，这种实现取最后一位的方式真的巧妙

引入lowbit后，我们就可以引入树状数组的概念了

树状数组的核心仅是一个数组，我们不妨叫其数组c，在阐明树状数组实现方式前，先看几个规律
从上图我们不难发现第一个规律，即
1.c[i]所管理的数字个数等于2的i的最后一位1所在位数的位置减一次方
比如：
c【3】：${2}^{2-1}=2个$22−1=2个 （3=11）
c【7】：${2}^{1-1}=1个$21−1=1个 （7=111）
c【8】：${2}^{4-1}=8个$24−1=8个 （8=1000）

再观察，有第二个规律
2.将i的所有1从右到左取出来，将每操作一次的结果所控制的数写成一个集合就会得到前i个数组成的集合
比如：
c【7】：（7=111）=> 去1 =>（6=110）=>去1=>（4=100）=>去一=>0(无效)

集合为｛1，2，3，4，5，6，7｝

c【3】：（3=11）=> 去1 =>（2=10）=>去1=>0(无效)

集合为｛1，2，3｝

继续观察，有第三个规律

2.将i不断加lowbit（i），最后一次合法的操作必然会到达那个管的点最多的点，且过程中会遍历到包含i的点

比如：
c【7】：（7=111）=>加001=>（8=1000）
c【3】：（3=11）=> 加01 =>（4=100）=> 加100=>1000(越界，非法)

以上规律理解后，我们就可以实现单点修改和区间查询了

• 单点修改

若要修改第x个数，则要修改管理x的所有点
而从以上规律再结合图中不难得出，只需要一直

x+=lowbit(x)

就可以遍历到管理x的所有点了

• 区间查询
  从规律1再结合图中不难得出，不断

x-=lowbit(x)

再将值加起来，就可以得解了

以上就是树状数组的核心，这也是其比线段树更加方便的原因之一

一道模版题的code（带注释） luogu P3374

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(register int i=start;i>=end;i--)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) ((a<b)?a:b)
#define ll long long
#define lowbit(a) (a&(-a))
const int maxn=500000+10;
int c[maxn];
int n,m;
template<typename T>T read(T &a)//fast read 
{
	T res=0;char r=getchar();bool neg=false;
	while(r>'9'||r<'0'){if(r=='-')neg=true;r=getchar();} 
	while(r<='9'&&r>='0'){res=res*10+r-'0';r=getchar();}
	a=(neg)?-res:res;
}
inline void addnum(int pos,int num)//在位置pos加上num
{
	int t=pos;
	while(t<=n)//将t一直+=lowbit(t)
	{
		c[t]+=num;
		t+=lowbit(t);
	}
}
int query(int r)//查询1到r的区间和
{
	int res=0;
	int x=r;
	while(x>0)//将t一直-=lowbit(t)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	//freopen("datain.txt","r",stdin);
	clean(c,0);
	read(n);read(m);
	int aa;
	loop(i,1,n)//初始化树状数组
	{
		read(aa);
		addnum(i,aa);
	}
	loop(i,1,m)
	{
		int op;read(op);
		if(op==1)
		{
			int p,num;
			read(p);
			read(num);
			addnum(p,num);
		}
		else if(op==2)
		{
			int l,r;
			read(l);
			read(r);
			printf("%d\n",query(r)-query(l-1));
		}
	}
	return 0;
}

另一道模版题luogu P3368

本题不可用以树状数组为主的思维去做
要用差分的思想
差分？
这个博客将本题的差分分析的不错

了解了差分之后，这个题其实就是要维护一个差分数组的前缀和，即

$f[i]=\sum_{j=1}^{i}$f[i]=∑j=1i​

这时才该想到树状数组
code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i>=end;i--)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) ((a<b)?a:b)
#define ll long long
#define lowbit(a) (a&(-a))
const int maxn=500000+10;
int c[maxn];
int data[maxn];
int n,m;
template<class T>void read(T &a)
{
	int res=0;bool neg=false;char r=getchar();
	while(r>'9'||r<'0'){if(r=='-')neg=true;r=getchar();}
	while(r>='0'&&r<='9'){res=res*10+r-'0';r=getchar();}
	a=(neg)?-res:res;
}
inline void addnum(int pos,int num)
{
	int x=pos;
	while(x<=n)
	{
		c[x]+=num;
		x+=lowbit(x);
	}
}
inline int query(int pos)
{
	int x=pos;int res=0;
	while(x>0)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	//freopen("datain.txt","r",stdin);
	read(n);
	read(m);
	clean(data,0);
	clean(c,0);
	loop(i,1,n)
	{
		read(data[i]);
		addnum(i,data[i]-data[i-1]);//维护差分数组
	}
	loop(i,1,m)
	{
		int op;read(op);
		if(op==1)
		{
			int x,y,k;read(x);read(y);read(k);
			addnum(x,k);addnum(y+1,-k);//维护差分数组
		}
		else if(op==2)
		{
			int x;read(x);
			printf("%d\n",query(x));//由题，直接输出前x项和即可
		}
	}
	return 0;
}