树状数组

树状数组

单点修改，区间查询

luogu P3347【模板】树状数组 1

int lowbit(int aa)
{
	return aa&-aa;
}
void add(int xx,int aa)
{
	for(int i=xx;i<=n;i+=lowbit(i))
		t[i]+=aa;
}
int ask(int xx)
{
	int now=0;
	for(int i=xx;i>0;i-=lowbit(i))
		now+=t[i];
	return now;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		add(i,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>k>>x>>y;
		if(k==1)
		{
			add(x,y);
		}
		if(k==2)
		{
			cout<<ask(y)-ask(x-1)<<"\n";
		}
	}
	return 0;
}

区间修改，单点查询

luogu P3368 【模板】树状数组 2

利用差分数组，原数组为$a$,差分数组为$cha$,令$cha_i=a_i-a_{i-1}$，对$[l,r]$区间整体加$k$，则让$cha_l+k$，让$cha_{r+1}-k$，这样对差分数组求前缀和即为$a_i$的值。

int lowbit(int aa)
{
	return aa&-aa;
}
void add(int xx,int aa)
{
	for(int i=xx;i<=n;i+=lowbit(i))
		t[i]+=aa;
}
ll ask(int xx)
{
	ll now=0;
	for(int i=xx;i>0;i-=lowbit(i))
		now+=t[i];
	return now;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		cha[i]=a[i]-a[i-1];
		add(i,cha[i]);
	}

	for(int i=1;i<=m;i++)
	{
		cin>>o;
		if(o==1){
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		if(o==2){
			cin>>x;
			cout<<ask(x)<<endl;
		}
	}
	return 0;
}

求逆序对

luogu P1908 逆序对

int lowbit(int aa)
{
	return aa&-aa;
}
void add(int xx,int aa)
{
	for(int i=xx;i<=n;i+=lowbit(i))
		t[i]+=aa;
}
int ask(int xx)
{
	int now=0;
	for(int i=xx;i>0;i-=lowbit(i))
		now+=t[i];
	return now;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	tot=unique(b+1,b+n+1)-b-1;  
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+tot+1,a[i])-b; //数据离散化，压缩空间
	for(int i=1;i<=n;i++)
	{
		add(a[i],1);
		ans+=(ask(tot)-ask(a[i]));
	}
	cout<<ans<<endl;
	return 0;
}

区间修改，区间查询

luogu P2357 守墓人

对$a$数组而言，设其差分数组为$cha$，则$a_i=\sum_{j=1}^{i}cha_j$，$a_r$ 的前缀和$pre_r=\sum_{i=1}^{r}a_i$，则$pre_r=\sum_{i=1}^{r}\sum_{j=1}^{i}cha_j$，即$pre_r=\sum_{i=1}^{r}cha_i \times (r-i+1)$，即$pre_r=\sum_{i=1}^rcha_i\times(r+1) - \sum_{i=1}^rcha_i\times i$，对于前后两个求和式，分别维护一个树状数组，即可实现区间修改与区间查询。

int lowbit(int x)
{
	return x&-x;
}
void add(int x,ll aa)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		cha[i]+=aa;
		cha2[i]+=aa*(x);
	}
}
ll ask(int x)
{
	ll now=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		now+=(cha[i]*(x+1)-cha2[i]);
	}
	return now;
}
int main()
{
	cin>>n>>f;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		add(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=f;i++)
	{
		cin>>o;
		if(o==1){
			cin>>l>>r>>k;
			add(l,k);
			add(r+1,-k);
		}
		if(o==2){
			cin>>k;
			add(1,k);
			add(2,-k);
		}
		if(o==3){
			cin>>k;
			add(1,-k);
			add(2,k);
		}
		if(o==4){
			cin>>l>>r;
			cout<<ask(r)-ask(l-1)<<"\n";
		}
		if(o==5){
			cout<<ask(1)<<"\n";
		}
	}
	return 0;
}