【题解】一本通线段树（合集）

前言

花了大概三天的时间，我终于做完了一本通的线段树专题，在这里汇总了五道题的题解，供参考。

区间和

原题：accoders，一本通，洛谷P3374

最简单的线段树，但是需要scanf和printf，另外需要开longlong。

#include <bits/stdc++.h>
#define int long long//需要开longlong，否则会RE
using namespace std;
const int N=100010;

struct node{
	int x,l,r;
}tree[4*N+10];//线段树需要四倍的空间
int a[N];//原数组

void build(int x,int l,int r){//建树，初始化
	tree[x].l=l,tree[x].r=r;
	if(l==r){//叶子结点
		tree[x].x=a[l];//直接赋值
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid),build(x*2+1,mid+1,r);//递归建树
	tree[x].x=tree[x*2].x+tree[x*2+1].x;//pushup操作
}
int query(int x,int l,int r){//区间查询
	if(tree[x].l>=l&&tree[x].r<=r) return tree[x].x;
	int sum=0;
	int mid=(tree[x].l+tree[x].r)/2;
	if(l<=mid) sum+=query(x*2,l,r);
	if(r>mid) sum+=query(x*2+1,l,r);
	return sum;//返回区间和
}
void change(int now,int x,int k){//单点修改
	if(tree[now].l==tree[now].r) tree[now].x+=k;//如果找到该节点，修改它
	else{
		int mid=(tree[now].l+tree[now].r)/2;//等价于<<1，但是加不加没有区别
		if(x<=mid) change(now*2,x,k);
		else change(now*2+1,x,k);
		tree[now].x=tree[now*2].x+tree[now*2+1].x;//pushup操作
	}
}
int n,q;
signed main(){
	scanf("%lld%lld",&n,&q);//需要用scnaf，否则会tle
	for(int i=1;i<=n;i++) a[i]=0;//初始化原数组
	build(1,1,n);//建树
	while(q--){
		int t,b,c;
		scanf("%lld%lld%lld",&t,&b,&c);
		if(t==0) change(1,b,c);
		else printf("%lld\n",query(1,b,c));
	}
}

A simple Problem with Integers

原题：Accoders，一本通，洛谷P3372

需要懒标记，另外需要开longlong

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
struct node{
	int sum;
	int l,r;
	int add;//懒标记
}tr[N*4+10];//线段树四倍空间
int a[N];
inline void pushup(int x){
	tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;//用inline可以优化速度
}
inline void pushudown(int x){//pushdown操作
	if(tr[x].add){//把懒标记分裂
		tr[2*x].add+=tr[x].add,tr[2*x+1].add+=tr[x].add;//把懒标记赋给左右儿子
		tr[2*x].sum+=tr[x].add*(tr[2*x].r-tr[2*x].l+1);
		tr[2*x+1].sum+=tr[x].add*(tr[2*x+1].r-tr[2*x+1].l+1);
		tr[x].add=0;//清空懒标记
	}
}
void build(int x,int l,int r){//建树
	tr[x].l=l,tr[x].r=r,tr[x].add=0;//把懒标记设为0
	if(l==r){
		tr[x].sum=a[l];//叶子结点直接赋值
		return;
	}
	int mid=(l+r)/2;
	build(2*x,l,mid),build(2*x+1,mid+1,r);//递归建树
	pushup(x);//pushup操作
}
int query(int x,int l,int r){//查询
	if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;//该节点区间在要查询的区间之内，直接返回值
	int sum=0;
	pushudown(x);//分裂懒标记
	int mid=(tr[x].l+tr[x].r)/2;
	if(l<=mid) sum+=query(x*2,l,r);
	if(r>mid) sum+=query(x*2+1,l,r);
	return sum;	
}
void update(int now,int l,int r,int k){//区间修改
	if(l<=tr[now].l&&r>=tr[now].r){//该节点区间在要修改的区间之内，直接修改懒标记
		tr[now].sum+=k*(tr[now].r-tr[now].l+1);
		tr[now].add+=k;
	}
	else{
		pushudown(now);//如果节点区间不在要修改的区间之内，那么分裂懒标记，传给子节点
		int mid=(tr[now].l+tr[now].r)/2;
		if(l<=mid) update(now*2,l,r,k);
		if(r>mid) update(now*2+1,l,r,k);	
		pushup(now);//pushup操作，该节点的值等于两个子节点值的和
	}
}
int n,q;
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);//建树
	while(q--){
		int l,r,k;
		char c;
		cin>>c>>l>>r;
		if(c=='C'){
			cin>>k;
			update(1,l,r,k);
		}
		else cout<<query(1,l,r)<<endl;
	}
	return 0;
}

最大数maxnumber

原题：Accoders，一本通

RMQ问题的解法很多，包括ST表、树状数组、单调队列，但是用线段树做也比较简单，只需要把模板中的求和操作换成取最大值就行。

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct node{
    int maxx;
    int l,r;
}tr[N*4+10];//线段树四倍空间
inline void pushup(int x){
    tr[x].maxx=max(tr[2*x].maxx,tr[2*x+1].maxx);//pushup操作
}
void build(int x,int l,int r){//建树
    tr[x].l=l,tr[x].r=r;
    if(l==r){
        tr[x].maxx=0;//子节点的最大值应该初始化为0
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid),build(2*x+1,mid+1,r);//递归建树
    //在这里就不需要pushup了
}
int query(int x,int l,int r){
    if(l<=tr[x].l&&r>=tr[x].r) return tr[x].maxx;//该节点区间在要查询的区间之内，直接返回值
    int maxx=-0x3f3f3f;
    int mid=(tr[x].l+tr[x].r)/2;
    if(l<=mid) maxx=max(maxx,query(x*2,l,r));
    if(r>mid) maxx=max(maxx,query(x*2+1,l,r));
    return maxx; //查询到的最大值应等于两子区间的最大的一个
}
void change(int now,int x,int k){
    if(tr[now].l==tr[now].r) tr[now].maxx=k;//找到该子节点，修改它
    else{
        int mid=(tr[now].l+tr[now].r)/2;
        if(x<=mid) change(now*2,x,k);
        else change(now*2+1,x,k);
        pushup(now);
    }
}
int m,p,cnt=0,a=0;
int main(){
    cin>>m>>p;
    build(1,1,m);
    while(m--){
        char c;
        int l;
        cin>>c>>l;
        if(c=='Q'){
            a=query(1,cnt-l+1,cnt);
            cout<<a<<endl;
        }
        else change(1,++cnt,(l+a)%p);//按照题目的要求来……真复杂
    }
}

花仔游历各国

Accoders，一本通，洛谷P4145

最开始我直接用单调修改、区间查询的暴力方法做的，不出意外的tle了，后来想到，一个数如果是1，那么它无论是开几次根号都得1，通过这个，我们就可以优化，优化后是73，改成scnaf变成了91。但是之后就怎么也成不了100，加了快速快写和O2后也过不了，后来在查询操作中加了一个类似于剪枝的操作，于是就过了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
	int l,r,sum,maxx;
}tr[N*4];//线段树四倍空间
int a[N];
int n,m;
inline int read(){//快速（开始的时候一直tle，就就加了一个快读快写，但还是tle）
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x){//快写（不用管它）
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
void pushup(int x){//pushup操作
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
	tr[x].maxx=max(tr[x<<1].maxx,tr[x<<1|1].maxx);//记录最大值，这样就能判断开完根号是不是1
}
void build(int x,int l,int r){
	tr[x].l=l,tr[x].r=r;
	if(l==r){//找到了叶子结点
		tr[x].sum=tr[x].maxx=a[l];//初始化
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);//递归建树
	pushup(x);
}
void change(int x,int l,int r){
	if(tr[x].maxx<=1) return;//如果开完根号等于1，那么就不用往下找了，因为1开几次根号都得1
	if(tr[x].l==tr[x].r){
		tr[x].sum=sqrt(tr[x].sum);//开根号，不用向下取整，因为c++会自动给你取整
		tr[x].maxx=sqrt(tr[x].maxx);
		return;
	}
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) change(x<<1,l,r);
	if(r>mid) change(x<<1|1,l,r);
	pushup(x);
}
int query(int x,int l,int r){
	if(tr[x].l>=l&&tr[x].r<=r) return tr[x].sum;
	int mid=(tr[x].l+tr[x].r)>>1,sum=0;
	if(l<=mid) sum=query(x<<1,l,r);
	if(r>mid) sum+=query(x<<1|1,l,r);
	return sum;
}
signed main(){
	int k,l,r;
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	cin>>m;
	while(m--){
		k=read(),l=read(),r=read();
		if(l>r) swap(l,r);
		if(k==2) change(1,l,r);
		else{
			write(query(1,l,r));
			putchar('\n');
		}
	}
	return 0;
}

维护序列seq

原题：Accoders，一本通，洛谷P2023

需要把区间中的数做加法或乘法，我们可以利用两个懒标记，先乘后加，因为如果把懒标记看成

$$mul \times sum+add$$

那么如果加上一个$add`$
那么就变成

$$mul \times sum+add+add`$$

如果乘上一个$mul`$
那就是

$$mul \times sum \times mul`+add \times mul$$

一点也不影响结果

反之如果是先加后乘就很麻烦，甚至会出错

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
struct node{
    int l,r;
    int sum,add,mul;
}tr[N*4+10];//线段树开四倍空间
int a[N];
int n,p,m;
inline void pushup(int x){
    tr[x].sum=(tr[2*x].sum+tr[2*x+1].sum)%p;
}
inline void eval(int x,int add,int mul){//我们把计算懒标记单独放在这个函数里，否则太不容易理解了
	/*先乘后加比较方便，因为
	我们把懒标记看成mul*sum+add
	那么如果加上一个add2那么就变成 mul*sum+add+add2
	如果乘上一个mul2那就是mul*sum*mul2+add*mul
	一点也不影响结果
	反之如果是先加后乘就很麻烦，甚至会出错
	*/
    tr[x].sum=(tr[x].sum*mul+add*(tr[x].r-tr[x].l+1))%p;
    tr[x].mul=(mul*tr[x].mul)%p;        
    tr[x].add=(tr[x].add*mul+add)%p;
}

inline void pushdown(int x){//懒标记
    eval(x*2,tr[x].add,tr[x].mul);
    eval(x*2+1,tr[x].add,tr[x].mul);
    tr[x].add=0,tr[x].mul=1;//清空的时候把加法懒标记初始化成0，但是乘法懒标记要初始化成1
}
void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;
    tr[x].add=0,tr[x].mul=1;//乘法懒标记要初始化为1
    if(l==r){
        tr[x].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid),build(x*2+1,mid+1,r);//递归建树
    pushup(x);
}
void change(int x,int l,int r,int add,int mul){
    if(l<=tr[x].l&&r>=tr[x].r) eval(x,add,mul);//计算懒标记
    else{
        pushdown(x);
        int mid=(tr[x].l+tr[x].r)/2;
        if(l<=mid) change(x*2,l,r,add,mul);
        if(r>mid) change(x*2+1,l,r,add,mul);
        pushup(x);
    }
}
int query(int x,int l,int r){
    if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;
    int sum=0;
    pushdown(x);//查找的过程中也要pushdown
    int mid=(tr[x].l+tr[x].r)/2;
    if(l<=mid) sum+=query(x*2,l,r)%p;
    if(r>mid) sum+=query(x*2+1,l,r)%p;
    return sum;
}
signed main(){
    int t,g,c,ch;
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>m;
    while(m--){
        cin>>ch>>t>>g;
        if(ch==1){
            cin>>c;
            change(1,t,g,0,c);          
        }
        else if(ch==2){
            cin>>c;
            change(1,t,g,c,1);          
        }
        else cout<<query(1,t,g)%p<<endl;
    }
    return 0;
}