线段树

P3372 【模板】线段树 1

已知一个数列ai，有下列两种操作

1. 将区间[x,y]内每个数加上k
2. 求区间[x,y]中每个数的和

线段树的思想便是将数列a，用若干个区间，在树上用结点表示

如图便是一棵线段树

线段树的性质

1. 对于任意一个结点，要么没子结点，要么有两个结点
2. 对于一个长度序列为n的数列，建立的线段树只有(2n-1)个结点
3. 对于一个长度序列为n的数列，树高为O(logn)

建树

采用递归方法

long long a[100010];//数列
long long w[400010];//w数组记录树
void pushup(int p){
    w[p]=w[p*2]+w[p*2+1];
}
void build(int p,int l,int r){
    if(l==r){//即到达叶子结点
        w[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);//合并区间和
}

p表示当前线段树结点的编号，w即区间和

区间修改+区间查询

这里引入延迟标记—-lazy tag,用来记录一些区间修改的信息。当递归至一个被完全包含的区间时，在这个区间打上一个lazy-tag,记录这个区间中的每个数都需要被加上某个数，然后直接修改该结点的区间和

而当新访问到一个结点时，先将延迟标记下放到子结点，然后再递归

long long lazytag[400010];
void maketag(int p,int length,long long x){
    lazytag[p]+=x;//修改当前的lazytag
    w[p]+=length*x;//修改区间和
}
void pushdown(int p,int l,int r){
    int mid=(l+r)/2;
    maketag(p*2,mid-l+1,lazytag[p]);//给左子树加上lazytag[p];
    maketag(p*2+1,r-mid,lazytag[p]);//同理
    lazytag[p]=0;//lazytag[p]已下放到下一层，故这层清0
}
long long query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)return w[p];//完全包含全返回
    if(l>qr||r<ql){
        return 0;//无相交
    }else{
        int mid=(l+r)/2;
        pushdown(p,l,r);
        return query(p*2,l,mid,ql,qr)+query(p*2+1,mid+1,r,ql,qr);
    }
}
void modify(int p,int l,int r,int ql,int qr,long long x){
    if(ql<=l&&qr>=r){
    	maketag(p,r-l+1,x);
	}else if(!(l>qr||r<ql)){
		int mid=(l+r)/2;
   	 	pushdown(p,l,r);
   		modify(p*2,l,mid,ql,qr,x);
   	 	modify(p*2+1,mid+1,r,ql,qr,x);
   	 	pushup(p);
	}
}

总代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010];//数列
long long w[400010];//w数组记录树
long long lazytag[400010];
void pushup(int p){
    w[p]=w[p*2]+w[p*2+1];
}
void build(int p,int l,int r){
    if(l==r){//即到达叶子结点
        w[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);//合并区间和
}
void maketag(int p,int length,long long x){
    lazytag[p]+=x;//修改当前的lazytag
    w[p]+=length*x;//修改区间和
}
void pushdown(int p,int l,int r){
    int mid=(l+r)/2;
    maketag(p*2,mid-l+1,lazytag[p]);//给左子树加上lazytag[p];
    maketag(p*2+1,r-mid,lazytag[p]);//同理
    lazytag[p]=0;//lazytag[p]已下放到下一层，故这层清0
}
long long query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)return w[p];//完全包含全返回
    if(l>qr||r<ql){
        return 0;//无相交
    }else{
        int mid=(l+r)/2;
        pushdown(p,l,r);
        return query(p*2,l,mid,ql,qr)+query(p*2+1,mid+1,r,ql,qr);
    }
}
void modify(int p,int l,int r,int ql,int qr,long long x){
    if(ql<=l&&qr>=r){
    	maketag(p,r-l+1,x);
	}else if(!(l>qr||r<ql)){
		int mid=(l+r)/2;
   	 	pushdown(p,l,r);
   		modify(p*2,l,mid,ql,qr,x);
   	 	modify(p*2+1,mid+1,r,ql,qr,x);
   	 	pushup(p);
	}
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        long long cnt,x,y,k;
        cin>>cnt;
        if(cnt==1){
            cin>>x>>y>>k;
            modify(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
	}
    return 0;
}