【模板】线段树 主席树

关于线段树的一些算法的模板的汇总。

Luogu P3372 【模板】线段树 1

普通的线段树，区间加法，区间查询。

#include<cstdio>
using namespace std;
const int maxn = 100005;
int n,m,x,y,flag;
int l[4*maxn],r[4*maxn];
long long lazy[8*maxn],sum[4*maxn];

void build(int L,int R,int now) {
    lazy[now] = 0;
    l[now] = L;
    r[now] = R;
    if(L == R) {
        scanf("%lld",&sum[now]);
        return;
    }
    int mid = (L+R)/2;
    build(L,mid,now*2);
    build(mid+1,R,now*2+1);
    sum[now] = sum[now*2] + sum[now*2+1];
}

long long query(int L,int R,int now) {
    sum[now] += lazy[now] * (r[now] - l[now] + 1);
    lazy[now*2] += lazy[now];
    lazy[now*2+1] += lazy[now];
    lazy[now] = 0;
    if(l[now] == L && r[now] == R)return sum[now];
    int mid = (l[now]+r[now])/2;
    if(R <= mid) return query(L,R,now*2);
    else if(L >= mid+1) return query(L,R,now*2+1);
    else return query(L,mid,now*2)+query(mid+1,R,now*2+1);
}

void modify(int L,int R,long long d,int now) {
    if(l[now] == L && r[now] == R) {
        lazy[now] += d;
        return;
    }
    sum[now] += (long long)d*(R-L+1);
    int mid = (l[now]+r[now])/2;
    if(R <= mid) modify(L,R,d,now*2);
    else if(L >= mid+1) modify(L,R,d,now*2+1);
    else {
        modify(L,mid,d,now*2);
        modify(mid+1,R,d,now*2+1);
    }
}

int main() {
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m) {
        m--;
        scanf("%d",&flag);
        if(flag == 1) {
            long long k;
            scanf("%d%d%lld",&x,&y,&k);
            modify(x,y,k,1);
        }
        if(flag == 2) {
            scanf("%d%d",&x,&y);
            printf("%lld
",query(x,y,1));
        }
    }
    return 0;
}

Luogu P3373 【模板】线段树 2

区间加法，区间乘法，区间查询。

注意：乘法标记优先于加法标记，打标记后直接（在原数的基础上）修改。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;
#define ls (now<<1)
#define rs (now<<1|1)
const int maxn = 1e6+10;
int n,q,p,op,x,y;
long long k;
int l[maxn<<2],r[maxn<<2];
long long sum[maxn<<2],a[maxn<<3],m[maxn<<3];

void build(int L,int R,int now) {
    l[now] = L;
    r[now] = R;
    m[now] = 1;
    a[now] = 0;
    if(L == R) {
        scanf("%lld",&k);
        sum[now] = k%p;
        return;
    }
    int mid = (l[now] + r[now])>>1;
    build(L,mid,ls);
    build(mid+1,R,rs);
    sum[now] = (sum[ls] + sum[rs])%p;
}

void pushdown(int now) {
    if(m[now]==1 && a[now]==0) return;
    m[ls] = (m[ls]*m[now])%p;
    m[rs] = (m[rs]*m[now])%p;
    a[ls] = (a[ls]*m[now] + a[now])%p;
    a[rs] = (a[rs]*m[now] + a[now])%p;
    sum[ls] = (sum[ls]*m[now] + a[now]*(long long)(r[ls]-l[ls]+1))%p;
    sum[rs] = (sum[rs]*m[now] + a[now]*(long long)(r[rs]-l[rs]+1))%p;
    m[now] = 1;
    a[now] = 0;
}

void modify(int L,int R,int now,long long A,long long M) {
    pushdown(now);
    if(l[now] == L && r[now] == R) {
        m[now] = (m[now]*M)%p;
        a[now] = (a[now]*M + A)%p;
        sum[now] = (sum[now]*M + A*(long long)(r[now]-l[now]+1))%p;
        return;
    }
    int mid = (l[now] + r[now])>>1;
    if(R <= mid) modify(L,R,ls,A,M);
    else if(L >= mid+1) modify(L,R,rs,A,M);
    else {
        modify(L,mid,ls,A,M);
        modify(mid+1,R,rs,A,M);
    }
    sum[now] = (sum[ls] + sum[rs])%p;
}

long long query(int L,int R,int now) {
    if(l[now] == L && r[now] == R) {
        return sum[now]%p;
    }
    pushdown(now);
    int mid = (l[now] + r[now])>>1;
    if(R <= mid) return query(L,R,ls)%p;
    else if(L >= mid+1) return query(L,R,rs)%p;
    else return (query(L,mid,ls) + query(mid+1,R,rs))%p;
}

int main() {
    scanf("%d%d%d",&n,&q,&p);
    build(1,n,1);
    while(q--) {
        scanf("%d%d%d",&op,&x,&y);
        if(op == 3)
            printf("%lld
",query(x,y,1));
        else {
            scanf("%lld",&k);
            if(op == 1) modify(x,y,1,0,k);
            if(op == 2) modify(x,y,1,k,1);
        }
    }
    return 0;
}

Luogu P3834 【模板】可持久化线段树 1（主席树）

这道模板题是求静态区间第$k$大的值。

对于每个前缀，建立一棵权值线段树，记录每个数字在当前的区间中出现了多少次，以及当前的区间中共有几个数字。

建树时，判断新加的数在左区间还是右区间，把当前的树不需要修改的儿子连向前一个状态，给另一个需要修改的儿子建立一个新节点，重复上一步。

查询时，用前缀和的方式求解。求出左区间共有多少个数（$sum[ls(v)]-sum[ls(u-1)]$），设为$lengthL$，然后与$k$的大小比较，

若$lengthL≥k$则在左儿子，否则在右儿子。注意，找右儿子时要把$k$减去左儿子已经找过的，即改为$k-lengthL$。

优化：给出的序列中可能不是每个数都出现的，一一对应效率较低，可以排序并去重。

（例如：给出1 2 5 5 8，可以直接建成(1)1,(2)2,(3)5,(4)8，而不是(1)1,(2)2,(3)3,(4)4,(5)5,(6)6,(7)7,(8)8 ）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MogeKo qwq
using namespace std;
const int maxn = 200005;
int a[maxn],b[maxn],T[maxn];
int L[maxn<<5],R[maxn<<5],sum[maxn<<5];
int cnt,n,q,m,t,u,v,k;

int build(int l,int r){
    int rt = ++cnt;
    int mid = (l+r)>>1;
    if(l < r){
        L[rt] = build(l,mid);
        R[rt] = build(mid+1,r);
    }
    return rt;
}
    
int update(int pre,int l,int r,int x){
    int rt = ++cnt;
    L[rt] = L[pre];
    R[rt] = R[pre];
    sum[rt] = sum[pre]+1;
    if(l < r){
        int mid = (l+r)>>1;
        if(x <= mid) L[rt] = update(L[pre],l,mid,x);
        else R[rt] = update(R[pre],mid+1,r,x);
    }
    return rt;
}

int query(int u,int v,int l,int r,int k){
    if(l == r)return l;
    int lenL = sum[L[v]] - sum[L[u]];
    int mid = (l+r)>>1;
    if(k <= lenL) return query(L[u],L[v],l,mid,k);
    else return query(R[u],R[v],mid+1,r,k-lenL);
}
    

int main(){
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    sort(b+1,b+n+1);
    m = unique(b+1,b+n+1)-(b+1);
    T[0] = build(1,m);
    for(int i = 1;i <= n;i++){
        t = lower_bound(b+1,b+m+1,a[i])-b;
        T[i] = update(T[i-1],1,m,t);
    }
    for(int i = 1;i <= q;i++){
        scanf("%d%d%d",&u,&v,&k);
        printf("%d
",b[query(T[u-1],T[v],1,m,k)]);
    }
    return 0;
}