跳到主要内容

树状数组

参考资料​

实现​

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

单点修改 + 区间查询

参考代码
#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

区间修改 + 单点查询

参考代码
#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

区间修改 + 区间查询

参考代码
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
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;
}

洛谷 P4514 上帝造题的七分钟​

洛谷 P4514 上帝造题的七分钟

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

  • 将矩形区域内的所有数字增加 vv。
  • 计算矩形区域内所有数字的总和。
参考代码
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=5000005;
bool vis[N];
ll pri[N],phi[N],mu[N];
unordered_map<ll,ll> sum_phi,sum_mu;
void init()
{
	vis[0]=vis[1]=1;
	phi[1]=mu[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			phi[i]=i-1;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				phi[i*pri[j]]=phi[i]*pri[j];
				mu[i*pri[j]]=0;
				break;
			}
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
			mu[i*pri[j]]=-mu[i];
		}
	}
	for(int i=1;i<N;i++)
	{
		phi[i]+=phi[i-1];
		mu[i]+=mu[i-1];
	}
}
ll sum_g(ll x)
{
	return x;
}
ll get_phi(ll x)
{
	if(x<N)return phi[x];
	if(sum_phi[x])return sum_phi[x];
	ll ans=x*(x+1)/2;
	for(ll l=2,r;l<=x;l=r+1)
	{
		r=x/(x/l);
		ans-=(sum_g(r)-sum_g(l-1))*get_phi(x/l);
	}
	return sum_phi[x]=ans/sum_g(1);
}
ll get_mu(ll x)
{
	if(x<N)return mu[x];
	if(sum_mu[x])return sum_mu[x];
	ll ans=1;
	for(ll l=2,r;l<=x;l=r+1)
	{
		r=x/(x/l);
		ans-=(sum_g(r)-sum_g(l-1))*get_mu(x/l);
	}
	return sum_mu[x]=ans/sum_g(1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	init();
	int T;
	cin>>T;
	while(T--)
	{
		ll n;
		cin>>n;
		cout<<get_phi(n)<<' '<<get_mu(n)<<'\n';
	}
	return 0;
}
最后于 更新