分块

实现

#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

区间修改 + 区间查询

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

洛谷 P2801 教主的魔法

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