静态BST区修区查

liujiaxi123456 · 2024-04-07 11:33:44 · 题解

关键词：静态BST区修区查

前言：

本文章为 P3372 【模板】线段树 1 的题解。

题解：

发现一个区间操作转到 BST 上，若目标区间全在左/右儿子，直接进去修改/查询即可，否则直接拆成两个指针去两个区间找。

看似好像会 TLE，但是发现第一次拆分后，若还要拆分，可以直接修改/查询整个子树的信息，所以总时间复杂度仍然保证。

拓展：

发现这个方法可以适用于所有平衡树，对于 Treap，Splay 虽然用处不大，但在 SGT 时就有很大作用了，所以建议学习一下。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn = 1e5+5;

namespace Josh_zmf {

    int N, Q, num, root, stk[Maxn]; ll a[Maxn];
    struct node { int lson, rson, size, id; ll val, sum, add; } tree[Maxn];

    inline void Add(int t, int addd) {
        tree[t].add += addd;
        tree[t].val += addd;
        tree[t].sum += 1ll*addd*tree[t].size;
    }

    inline void pushdown(int t) {
        if(tree[t].add) {
            Add(tree[t].lson, tree[t].add), Add(tree[t].rson, tree[t].add);
            tree[t].add = 0;
        }
    }

    inline void pushup(int t) {
        tree[t].sum = tree[tree[t].lson].sum + tree[t].val + tree[tree[t].rson].sum;
        tree[t].size = tree[tree[t].lson].size + 1 + tree[tree[t].rson].size;
    }

    inline void Build(int &t, int l, int r) {
        if(l > r)   return ;
        t = ++num, tree[t].size = 1;
        if(l == r)  return tree[t].id = l, tree[t].sum = tree[t].val = a[l], void();
        int mid = (l+r)>>1; tree[t].id = mid, tree[t].val = a[mid];
        Build(tree[t].lson, l, mid-1), Build(tree[t].rson, mid+1, r);
        pushup(t);
    }

    inline void Modify(int l, int r, int addd) {
        int top = 0;
        for(int t=root; 1; t=(r<tree[t].id ?tree[t].lson :tree[t].rson)) {
            pushdown(t);
            stk[++top] = t;//, tree[t].val += addd;
            (l<=tree[t].id && tree[t].id<=r ?tree[t].val+=addd :false);
            (l == tree[t].id ?l++ :false);
            (r == tree[t].id ?r-- :false);
            if(l > r)   break;
            if(l < tree[t].id && tree[t].id < r) {
                // tree[t].val += addd;
                for(int u=tree[t].lson; 1; ) {
                    pushdown(u);
                    stk[++top] = u;//, tree[u].val += addd;
                    if(l < tree[u].id)  tree[u].val += addd, Add(tree[u].rson, addd), u = tree[u].lson;
                    else if(l == tree[u].id) { tree[u].val += addd, Add(tree[u].rson, addd); break; }
                    else    u = tree[u].rson;
                }
                for(int u=tree[t].rson; 1; ) {
                    pushdown(u);
                    stk[++top] = u;//, tree[u].val += addd;
                    if(tree[u].id < r)  tree[u].val += addd, Add(tree[u].lson, addd), u = tree[u].rson;
                    else if(tree[u].id == r) { tree[u].val += addd, Add(tree[u].lson, addd); break; }
                    else    u = tree[u].lson;
                }
                break;
            }   
        }
        for(; top; pushup(stk[top--]));
    }

    inline ll Query(int l, int r) {
        ll res = 0;
        for(int t=root; 1; t=(r<tree[t].id ?tree[t].lson :tree[t].rson)) {
            pushdown(t);//, res += tree[t].val;
            (l<=tree[t].id && tree[t].id<=r ?res+=tree[t].val :false);  
            (l == tree[t].id ?l++ :false);
            (r == tree[t].id ?r-- :false);
            if(l > r)   break;
            if(l < tree[t].id && tree[t].id < r) {
                // res += tree[t].val;
                for(int u=tree[t].lson; 1; ) {
                    pushdown(u);//, res += tree[u].val;
                    if(l < tree[u].id)  res += tree[u].val + tree[tree[u].rson].sum, u = tree[u].lson;
                    else if(l == tree[u].id) { res += tree[u].val + tree[tree[u].rson].sum; break; }
                    else    u = tree[u].rson;
                }
                for(int u=tree[t].rson; 1; ) {
                    pushdown(u);//, res += tree[u].val;
                    if(tree[u].id < r)  res += tree[u].val + tree[tree[u].lson].sum, u = tree[u].rson;
                    else if(tree[u].id == r) { res += tree[u].val + tree[tree[u].lson].sum; break; }
                    else    u = tree[u].lson;
                }
                break;
            }
        }
        return res;
    }

    int main() {
        cin>> N>> Q;
        for(int i=1; i<=N; i++) cin>> a[i];
        Build(root, 1, N);
        for(int opt, x, y, k; Q--; ) {
            cin>> opt>> x>> y;
            if(opt == 1)    cin>> k, Modify(x, y, k);
            else    cout<< Query(x, y)<< '\n';
        }
        return 0;
    }

}

int main() {
    Josh_zmf::main();
    return 0;
}

结语：

点个赞再走吧！：）