分块

实现

#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;
}

例题

洛谷 P3372 【模板】线段树 1

区间修改 + 区间查询

Reference Code

分块
树状数组
线段树

#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;
}

#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;
}

#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;
}

洛谷 P2801 教主的魔法

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \ldots, N$ 。

每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次可以把闭区间 $[L, R]$ （ $1≤L≤R≤N$ ）内的英雄的身高全部加上一个整数 $W$ 。（虽然 $L=R$ 时并不符合区间的书写规范，但我们可以认为是单独增加第 $L(R)$ 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$ ，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。

Reference Code

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

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1000005;
int a[N],b[N],t[N];
int id[N],st[N],ed[N];
void reset(int k)
{
	for(int i=st[k];i<=ed[k];i++)t[i]=a[i];
	sort(t+st[k],t+ed[k]+1);
}
void init(int n)
{
    int len=sqrt(n);
	for(int i=1;i<=len;i++)
	{
		st[i]=n/len*(i-1)+1;
		ed[i]=n/len*i;
	}
	ed[len]=n;
	for(int i=1;i<=len;i++)
	{
		for(int j=st[i];j<=ed[i];j++)id[j]=i;
	}
	for(int i=1;i<=len;i++)
	{
		reset(i);
	}
}
void update(int l,int r,int v)
{
	int x=id[l],y=id[r];
	if(x==y)
	{
		for(int i=l;i<=r;i++)a[i]+=v;
		reset(x);
		return;
	}
	for(int i=l;i<=ed[x];i++)a[i]+=v;
	for(int i=st[y];i<=r;i++)a[i]+=v;
	for(int i=x+1;i<y;i++)b[i]+=v;
	reset(x);
	reset(y);
}
int query(int l,int r,int v)
{
	int x=id[l],y=id[r];
	int ans=0;
	if(x==y)
	{
		for(int i=l;i<=r;i++)if(a[i]+b[x]>=v)ans++;
		return ans;
	}
	for(int i=l;i<=ed[x];i++)if(a[i]+b[x]>=v)ans++;
	for(int i=st[y];i<=r;i++)if(a[i]+b[y]>=v)ans++;
	for(int i=x+1;i<=y-1;i++)ans+=ed[i]-(lower_bound(t+st[i],t+ed[i]+1,v-b[i])-t)+1;
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    }
    init(n);
    while(q--)
    {
    	char op;
    	int l,r,v;
    	cin>>op>>l>>r>>v;
    	if(op=='M')update(l,r,v);
    	else if(op=='A')cout<<query(l,r,v)<<'\n';
	}
	return 0;
}

实现​

例题​

洛谷 P3372 【模板】线段树 1​

洛谷 P2801 教主的魔法​

实现

例题

洛谷 P3372 【模板】线段树 1

洛谷 P2801 教主的魔法