树状数组

参考资料

• 树状数组 - OI Wiki

实现

struct BIT
{
	int c[N];
	void add(int u,int v){while(u<N){c[u]+=v;u+=u&-u;}}
	int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
};

例题

洛谷 P3374 【模板】树状数组 1

洛谷 P3374 【模板】树状数组 1

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$；
• 求出某区间每一个数的和。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
int c[N];
void add(int u,int v)
{
	while(u<N)
	{
		c[u]+=v;
		u+=u&-u;
	}
}
int sum(int u)
{
	int res=0;
	while(u)
	{
		res+=c[u];
		u-=u&-u;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		add(i,x);
	}
	while(m--)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)add(x,y);
		else if(op==2)cout<<sum(y)-sum(x-1)<<'\n';
	}
	return 0;
}

洛谷 P3368 【模板】树状数组 2

洛谷 P3368 【模板】树状数组 2

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；
2. 求出某一个数的值。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
int c[N];
void add(int u,int v)
{
	while(u<N)
	{
		c[u]+=v;
		u+=u&-u;
	}
}
int sum(int u)
{
	int res=0;
	while(u)
	{
		res+=c[u];
		u-=u&-u;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	int tmp=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		add(i,x-tmp);
		tmp=x;
	}
	while(m--)
	{
		int op,x,y,k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else if(op==2)
		{
			cin>>x;
			cout<<sum(x)<<'\n';
		}
	}
	return 0;
}

洛谷 P3372 【模板】线段树 1

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 $\{a_i\}$，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

Code (5)

三叉树

#include <bits/stdc++.h>
#define s1 (u*3)
#define s2 (u*3+1)
#define s3 (u*3+2)
#define m1 (l+(r-l)/3)
#define m2 (r-(r-l)/3)
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<4],tag[N<<4];
void gx(int u,ll v,int len)
{
	val[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	val[u]=val[s1]+val[s2]+val[s3];
}
void push_down(int u,int l,int r)
{
	if(!tag[u])return;
	if(l<=m1)gx(s1,tag[u],m1-l+1);
	if(m1<m2)gx(s2,tag[u],m2-m1);
	if(r>m2)gx(s3,tag[u],r-m2);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	if(l<=m1)build(s1,l,m1);
	if(m1<m2)build(s2,m1+1,m2);
	if(r>m2)build(s3,m2+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x>r||y<l)return;
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(l<=m1)update(s1,l,m1,x,y,v);
	if(m1<m2)update(s2,m1+1,m2,x,y,v);
	if(r>m2)update(s3,m2+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(l<=m1)res+=query(s1,l,m1,x,y);
	if(m1<m2)res+=query(s2,m1+1,m2,x,y);
	if(r>m2)res+=query(s3,m2+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

分块

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],b[N],s[N];
int id[N],len;
void update(int l,int r,ll v)
{
	int x=id[l],y=id[r];
	if(x==y)
	{
		for(int i=l;i<=r;i++){a[i]+=v;s[x]+=v;}
		return;
	}
	for(int i=l;id[i]==x;i++){a[i]+=v;s[x]+=v;}
	for(int i=r;id[i]==y;i--){a[i]+=v;s[y]+=v;}
	for(int i=x+1;i<y;i++){b[i]+=v;s[i]+=v*len;}
}
ll query(int l,int r)
{
	int x=id[l],y=id[r];
	ll res=0;
	if(x==y)
	{
		for(int i=l;i<=r;i++)res+=a[i]+b[x];
		return res;
	}
	for(int i=l;id[i]==x;i++)res+=a[i]+b[x];
	for(int i=r;id[i]==y;i--)res+=a[i]+b[y];
	for(int i=x+1;i<y;i++)res+=s[i];
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		id[i]=(i-1)/len+1;
		s[id[i]]+=a[i];
	}
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(x,y)<<'\n';
		}
	}
	return 0;
}

四叉树

#include <bits/stdc++.h>
#define s1 (u<<2)
#define s2 (u<<2|1)
#define s3 (u<<2|2)
#define s4 (u<<2|3)
#define m1 (l+(r-l>>2))
#define m2 (l+r>>1)
#define m3 (r-(r-l>>2))
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<5],tag[N<<5];
void gx(int u,ll v,int len)
{
	val[u]+=v*len;
	tag[u]+=v;
}
void push_up(int u)
{
	val[u]=val[s1]+val[s2]+val[s3]+val[s4];
}
void push_down(int u,int l,int r)
{
	if(!tag[u])return;
	if(l<=m1)gx(s1,tag[u],m1-l+1);
	if(m1<m2)gx(s2,tag[u],m2-m1);
	if(m2<m3)gx(s3,tag[u],m3-m2);
	if(r>m3)gx(s4,tag[u],r-m3);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	if(l<=m1)build(s1,l,m1);
	if(m1<m2)build(s2,m1+1,m2);
	if(m2<m3)build(s3,m2+1,m3);
	if(r>m3)build(s4,m3+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x>r||y<l)return;
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(l<=m1)update(s1,l,m1,x,y,v);
	if(m1<m2)update(s2,m1+1,m2,x,y,v);
	if(m2<m3)update(s3,m2+1,m3,x,y,v);
	if(r>m3)update(s4,m3+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(l<=m1)res+=query(s1,l,m1,x,y);
	if(m1<m2)res+=query(s2,m1+1,m2,x,y);
	if(m2<m3)res+=query(s3,m2+1,m3,x,y);
	if(r>m3)res+=query(s4,m3+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

树状数组

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
ll c1[N],c2[N];
void add(int u,ll v)
{
	ll w=u*v;
	while(u<N)
	{
		c1[u]+=v;
		c2[u]+=w;
		u+=u&-u;
	}
}
ll sum(ll *c,int u)
{
	ll res=0;
	while(u)
	{
		res+=c[u];
		u-=u&-u;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		add(i,x);
		add(i+1,-x);
	}
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<sum(c1,y)*(y+1)-sum(c1,x-1)*x-(sum(c2,y)-sum(c2,x-1))<<'\n';
		}
	}
	return 0;
}

线段树

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=100005;
ll a[N],val[N<<2],tag[N<<2];
void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
void push_up(int u){val[u]=val[ls]+val[rs];}
void push_down(int u,int l,int r)
{
	gx(ls,tag[u],mid-l+1);
	gx(rs,tag[u],r-mid);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r){val[u]=a[l];return;}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
	if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
	push_down(u,l,r);
	if(x<=mid)update(ls,l,mid,x,y,v);
	if(y>mid)update(rs,mid+1,r,x,y,v);
	push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)return val[u];
	push_down(u,l,r);
	ll res=0;
	if(x<=mid)res+=query(ls,l,mid,x,y);
	if(y>mid)res+=query(rs,mid+1,r,x,y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}

洛谷 P4514 上帝造题的七分钟

洛谷 P4514 上帝造题的七分钟

维护一个二维矩阵，需要支持以下两种操作：

• 将矩形区域内的所有数字增加 $v$。
• 计算矩形区域内所有数字的总和。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=2050;
struct BIT
{
	int c[N][N];
	void add(int x,int y,int v)
	{
		if(!x||!y)return;
		for(int i=x;i<N;i+=i&-i)
		{
			for(int j=y;j<N;j+=j&-j)
			{
				c[i][j]+=v;
			}
		}
	}
	int query(int x,int y)
	{
		int res=0;
		for(int i=x;i;i-=i&-i)
		{
			for(int j=y;j;j-=j&-j)
			{
				res+=c[i][j];
			}
		}
		return res;
	}
}A,B,C,D;
int n,m;
void add(int x,int y,int v)
{
	A.add(x,y,v*x*y);
	B.add(x,y,v*x);
	C.add(x,y,v*y);
	D.add(x,y,v);
}
int query(int x,int y)
{
	return A.query(x,y)+y*(B.query(x,m)-B.query(x,y))+x*(C.query(n,y)-C.query(x,y))+x*y*(D.query(n,m)-D.query(x,m)-D.query(n,y)+D.query(x,y));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	char op;
	cin>>op>>n>>m;
	while(cin>>op)
	{
		int a,b,c,d,v;
		if(op=='L')
		{
			cin>>a>>b>>c>>d>>v;
			add(c,d,v);
			add(a-1,d,-v);
			add(c,b-1,-v);
			add(a-1,b-1,v);
		}
		else if(op=='k')
		{
			cin>>a>>b>>c>>d;
			cout<<query(c,d)-query(a-1,d)-query(c,b-1)+query(a-1,b-1)<<'\n';
		}
	}
	return 0;
}