线段树区间操作集合

2023-10-05 23:31:10

这里放蒟蒻 lrj124 碰到的线段树区间操作集合

No.1

区间加

懒标记！

/************************************************
*Author        :  lrj124
*Created Time  :  2019.04.04.14:17
*Mail          :  1584634848@qq.com
*Problem       :  seg
************************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
int n,m;
struct seg { int l,r;  ll mark,sum; } tree[maxn<<2];
inline void pushup(int root) { tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum; }
inline void pushdown(int root) {
    if (tree[root].mark) {
        tree[root<<1].mark += tree[root].mark;
        tree[root<<1|1].mark += tree[root].mark;
        tree[root<<1].sum += tree[root].mark*(tree[root<<1].r-tree[root<<1].l+1);
        tree[root<<1|1].sum += tree[root].mark*(tree[root<<1|1].r-tree[root<<1|1].l+1);
        tree[root].mark = 0;
    }
}
inline void Build(int l,int r,int root) {
    tree[root].l = l;
    tree[root].r = r;
    if (l == r) {
        scanf("%lld",&tree[root].sum);
        return;
    }
    int mid = l+r>>1;
    Build(l,mid,root<<1);
    Build(mid+1,r,root<<1|1);
    pushup(root);
}
inline void update(int l,int r,int ql,int qr,int root,ll x) {
    if (qr < l || ql > r) return;
    if (ql <= l && r <= qr) {
        tree[root].mark += x;
        tree[root].sum += x*(r-l+1);
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    update(l,mid,ql,qr,root<<1,x);
    update(mid+1,r,ql,qr,root<<1|1,x);
    pushup(root);
}
inline ll query(int l,int r,int ql,int qr,int root) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return tree[root].sum;
    pushdown(root);
    int mid = l+r>>1;
    return query(l,mid,ql,qr,root<<1)+query(mid+1,r,ql,qr,root<<1|1);
}
int main() {
    //freopen("seg.in","r",stdin);
    //freopen("seg.out","w",stdout);
    scanf("%d%d",&n,&m);
    Build(1,n,1);
    while (m--) {
        int op,x,y;
        ll k;
        scanf("%d%d%d",&op,&x,&y);
        if (op == 1) {
            scanf("%lld",&k);
            update(1,n,x,y,1,k);
        } else printf("%lld\n",query(1,n,x,y,1));
    }
    return 0;
}

No.2

区间加，区间乘

加一个乘法标记就行了。

#include <cstdio>
const int maxn = 100000 + 10;
struct Seg { long long l,r,sum,add,mul; } tree[maxn*4];
long long p;
long long n,m;
inline void pushup(long long root) { tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum; tree[root].sum %= p; }
inline void BuildTree(long long l,long long r,long long root) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].mul = 1;
    if (l == r) {
        scanf("%lld",&tree[root].sum);
        tree[root].sum %= p;
        return;
    }
    long long mid = l+r>>1;
    BuildTree(l,mid,root<<1);
    BuildTree(mid+1,r,root<<1|1);
    pushup(root);
}
inline void pushdown(long long root) {
    if (tree[root].mul != 1) {
        tree[root<<1].mul = tree[root<<1].mul*tree[root].mul%p;
        tree[root<<1|1].mul = tree[root<<1|1].mul*tree[root].mul%p;
        tree[root<<1].add = tree[root<<1].add*tree[root].mul%p;
        tree[root<<1|1].add = tree[root<<1|1].add*tree[root].mul%p;
        tree[root<<1].sum = tree[root<<1].sum*tree[root].mul%p;
        tree[root<<1|1].sum = tree[root<<1|1].sum*tree[root].mul%p;
        tree[root].mul = 1;
    }
    if (tree[root].add != 0) {
        tree[root<<1].add = (tree[root<<1].add+tree[root].add)%p;
        tree[root<<1|1].add = (tree[root<<1|1].add+tree[root].add)%p;
        tree[root<<1].sum = (tree[root<<1].sum+tree[root].add*(tree[root<<1].r-tree[root<<1].l+1))%p;
        tree[root<<1|1].sum = (tree[root<<1|1].sum+tree[root].add*(tree[root<<1|1].r-tree[root<<1|1].l+1))%p;
        tree[root].add = 0;
    }
}
inline void UpdateAdd(long long ql,long long qr,long long l,long long r,long long root,long long x) {
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
        tree[root].add = (tree[root].add+x)%p;
        tree[root].sum = (tree[root].sum+x*(r-l+1))%p;
        return;
    }
    pushdown(root);
    long long mid = l+r>>1;
    UpdateAdd(ql,qr,l,mid,root<<1,x);
    UpdateAdd(ql,qr,mid+1,r,root<<1|1,x);
    pushup(root);
}
inline void UpdateMul(long long ql,long long qr,long long l,long long r,long long root,long long x) {
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
        tree[root].add = tree[root].add*x%p;
        tree[root].mul = tree[root].mul*x%p;
        tree[root].sum = tree[root].sum*x%p;
        return;
    }
    pushdown(root);
    long long mid = l+r>>1;
    UpdateMul(ql,qr,l,mid,root<<1,x);
    UpdateMul(ql,qr,mid+1,r,root<<1|1,x);
    pushup(root);
}
inline long long Query(long long ql,long long qr,long long l,long long r,long long root) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && qr >= r) return tree[root].sum;
    pushdown(root);
    long long mid = l+r>>1;
    return (Query(ql,qr,l,mid,root<<1)+Query(ql,qr,mid+1,r,root<<1|1))%p;
}
int main() {
    scanf("%lld%lld%lld",&n,&m,&p);
    BuildTree(1,n,1);
    while (m--) {
        long long val;
        long long op,l,r;
        scanf("%lld%lld%lld",&op,&l,&r);
        if (op == 1) {
            scanf("%lld",&val);
            UpdateMul(l,r,1,n,1,val);
        } else if (op == 2) {
            scanf("%lld",&val);
            UpdateAdd(l,r,1,n,1,val);
        } else printf("%lld\n",Query(l,r,1,n,1));
    }
    return 0;
}

No.3

把区间中等于 \(x\) 的数改成 \(y\)

对每个数开一个 tag，表示每个数会映射到哪个数。

/************************************************
*Author        :  lrj124
*Created Time  :  2019.10.04.14:07
*Mail          :  1584634848@qq.com
*Problem       :  cf911g
************************************************/
#include <cstdio>
const int maxn = 200000 + 10;
int n,q,a[maxn],tag[maxn<<2][101];
inline void pushdown(int root) {
    for (int i = 1;i <= 100;i++) {
        tag[root<<1][i] = tag[root][tag[root<<1][i]];
        tag[root<<1|1][i] = tag[root][tag[root<<1|1][i]];
    }
    for (int i = 1;i <= 100;i++) tag[root][i] = i;
}
inline void update(int l,int r,int ul,int ur,int num,int root,int x) {
    if (l > ur || r < ul) return;
    if (ul <= l && r <= ur) {
        for (int i = 1;i <= 100;i++)
            if (tag[root][i] == num) tag[root][i] = x;
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    update(l,mid,ul,ur,num,root<<1,x);
    update(mid+1,r,ul,ur,num,root<<1|1,x);
}
inline void print(int l,int r,int root) {
    if (l == r) {
        printf("%d ",tag[root][a[l]]);
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    print(l,mid,root<<1);
    print(mid+1,r,root<<1|1);
}
int main() {
//  freopen("cf911g.in","r",stdin);
//  freopen("cf911g.out","w",stdout);
    scanf("%d",&n);
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for (int i = 1;i <= n<<2;i++) for (int j = 1;j <= 100;j++) tag[i][j] = j;
    for (scanf("%d",&q);q--;) {
        int l,r,x,y;
        scanf("%d%d%d%d",&l,&r,&x,&y);
        update(1,n,l,r,x,1,y);
    }
    print(1,n,1);
    return 0;
}

No.4

区间每个数开方

就是暴力递归到每个叶子节点，若当前区间 Max 小于 2 就 return

/************************************************
*Author        :  lrj124
*Created Time  :  2019.09.28.14:24
*Mail          :  1584634848@qq.com
*Problem       :  luogu4145
************************************************/
#include <algorithm>
#include <cstdio>
#include <cmath>
using ll = long long;
const int maxn = 100000 + 10;
ll sum[maxn<<2],maxv[maxn<<2];
inline void pushup(int root) {
    sum[root] = sum[root<<1]+sum[root<<1|1];
    maxv[root] = std :: max(maxv[root<<1],maxv[root<<1|1]);
}
inline void build(int l,int r,int root) {
    if (l == r) {
        scanf("%lld",&sum[root]);
        maxv[root] = sum[root];
        return;
    }
    int mid = l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
inline void update(int l,int r,int ul,int ur,int root) {
    if (l > ur || r < ul || maxv[root] < 2) return;
    if (l == r) {
        maxv[root] = sum[root] = sqrt(sum[root]);
        return;
    }
    int mid = l+r>>1;
    update(l,mid,ul,ur,root<<1);
    update(mid+1,r,ul,ur,root<<1|1);
    pushup(root);
}
inline ll query(int l,int r,int ql,int qr,int root) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[root];
    int mid = l+r>>1;
    return query(l,mid,ql,qr,root<<1)+query(mid+1,r,ql,qr,root<<1|1);
}
int main() {
    for (int n,q,x,y,z;scanf("%d",&n) ^ EOF;puts("")) {
        build(1,n,1);
        for (scanf("%d",&q);q--;) {
            scanf("%d%d%d",&x,&y,&z);
            if (y > z) std :: swap(y,z);
            if (x) printf("%lld\n",query(1,n,y,z,1));
            else update(1,n,y,z,1);
        }
    }
    return 0;
}

No.5

区间取 Min,Max

把 pushup 改一改就行，
区间和 \(x\) 取 Max 时，区间最大和区间最小都和 \(x\) 取 Max
区间和 \(x\) 取 Min 时，区间最大和区间最小都和 \(x\) 取 Min

/************************************************
*Author        :  lrj124
*Created Time  :  2019.10.03.21:38
*Mail          :  1584634848@qq.com
*Problem       :  luogu4560
************************************************/
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 2000000 + 10;
int n,q,maxv[maxn<<2],minv[maxn<<2];
inline void pushup_max(int root,int x) {
    minv[root] = max(minv[root],x);
    maxv[root] = max(maxv[root],x);
}
inline void pushup_min(int root,int x) {
    minv[root] = min(minv[root],x);
    maxv[root] = min(maxv[root],x);
}
inline void pushdown(int root) {
    pushup_max(root<<1,maxv[root]);
    pushup_max(root<<1|1,maxv[root]);
    pushup_min(root<<1,minv[root]);
    pushup_min(root<<1|1,minv[root]);
    maxv[root] = 0; minv[root] = 999999;
}
inline void take_max(int l,int r,int ul,int ur,int root,int x) {
    if (l > ur || r < ul) return;
    if (ul <= l && r <= ur) {
        pushup_max(root,x);
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    take_max(l,mid,ul,ur,root<<1,x);
    take_max(mid+1,r,ul,ur,root<<1|1,x);
}
inline void take_min(int l,int r,int ul,int ur,int root,int x) {
    if (l > ur || r < ul) return;
    if (ul <= l && r <= ur) {
        pushup_min(root,x);
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    take_min(l,mid,ul,ur,root<<1,x);
    take_min(mid+1,r,ul,ur,root<<1|1,x);
}
inline void print(int l,int r,int root) {
    if (l == r) {
        printf("%d\n",maxv[root]);
        return;
    }
    pushdown(root);
    int mid = l+r>>1;
    print(l,mid,root<<1);
    print(mid+1,r,root<<1|1);
}
int main() {
    for (scanf("%d%d",&n,&q);q--;) {
        int op,l,r,w;
        scanf("%d%d%d%d",&op,&l,&r,&w);
        if (op == 1) take_max(1,n,l+1,r+1,1,w);
        else take_min(1,n,l+1,r+1,1,w);
    }
    print(1,n,1);
    return 0;
}

No.6

单点修改，区间询问最大连续子段和

只需要维护四个数：
max,lmax,rmax,sum
分别表示区间最大连续子段和，区间左缀最大连续和，区间右缀最大连续和，区间和
lmax = max(lmax,rson.sum+rson.lmax)
rmax = max(rmax,lson.sum+lson.rmax)
max = max(lson.max,rson.max,lson.rmax+rson.lmax)

/************************************************
*Author        :  lrj124
*Created Time  :  2019.09.15.08:38
*Mail          :  1584634848@qq.com
*Problem       :  spoj1716
************************************************/
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 50000 + 10;
struct seg { int l,r,sum,max; } tree[maxn<<2];
int n,q;
inline void pushup(int root) {
    tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;
    tree[root].l = max(tree[root<<1].l,tree[root<<1|1].l+tree[root<<1].sum);
    tree[root].r = max(tree[root<<1|1].r,tree[root<<1].r+tree[root<<1|1].sum);
    tree[root].max = max(tree[root<<1].r+tree[root<<1|1].l,max(tree[root<<1].max,tree[root<<1|1].max));
}
inline void build(int l,int r,int root) {
    if (l == r) {
        int x; scanf("%d",&x);
        tree[root] = { x,x,x,x };
        return;
    }
    int mid = l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
inline void update(int l,int r,int num,int root,int x) {
    if (l > num || r < num) return;
    if (l == r) {
        tree[root] = { x,x,x,x };
        return;
    }
    int mid = l+r>>1;
    update(l,mid,num,root<<1,x);
    update(mid+1,r,num,root<<1|1,x);
    pushup(root);
}
inline seg query(int l,int r,int ql,int qr,int root) {
    if (ql <= l && r <= qr) return tree[root];
    int mid = l+r>>1;
    if (mid >= qr) return query(l,mid,ql,qr,root<<1);
    if (ql > mid) return query(mid+1,r,ql,qr,root<<1|1);
    seg lson = query(l,mid,ql,qr,root<<1),rson = query(mid+1,r,ql,qr,root<<1|1),ans;
    ans = { max(lson.l,rson.l+lson.sum),max(rson.r,lson.r+rson.sum),rson.sum+lson.sum,max(lson.r+rson.l,max(lson.max,rson.max)) };
    return ans;
}
int main() {
//  freopen("spoj1716.in","r",stdin);
//  freopen("spoj1716.out","w",stdout);
    scanf("%d",&n);
    build(1,n,1);
    for (scanf("%d",&q);q--;) {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        if (x == 0) update(1,n,y,1,z);
        else printf("%d\n",query(1,n,y,z,1).max);
    }
    return 0;
}
上一篇：线段树区间修改+查询区间和


下一篇：SDOI2017相关分析