Phantom Bird

外观

线段树板子

约 454 字大约 2 分钟

OI

2025-11-23

维护群 (T,⊕)(T, \oplus)，⊕\oplus 有单位元 OO，懒标记信息为 STAT\text{STAT}

struct segtree {
    // === 数据 ===
    T a[maxn * 4];
    STAT lz[maxn * 4];

    // === 辅助函数 ===
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1) | 1; }
    inline int md(int x, int y) { return (x+y)>>1; }

    // === 维护 ===
    inline void pushup(int tn) {
        a[tn] = a[lc(tn)] ⊕ a[rc(tn)];
    }

    inline void pushdown(int tn) {
        int lcn=lc(tn), rcn=rc(tn);
        update a[lcn], lz[lcn] with lz[tn];
        update a[rcn], lz[rcn] with lz[tn];
        // 取决于具体懒标记类型
        lz[tn] = CLEAR;
    }

    // === 建树 ===
    void build(int tn, int tl, int tr) {
        if (tl == tr) {
            a[tn] = get(tl);
            return;
        }

        int mid = md(tl, tr);
        build(lc(tn), tl, mid);
        build(rc(tn), mid+1, tr);
        pushup(tn);
    }

    // === 单点操作 ===
    void modify1(int tn, int tl, int tr, int i, MODIFY m) {
        if (tl == tr) {
            modify a[tn] with m;
            return;
        }

        pushdown(tn);

        int mid = md(tl, tr);  // 谁懂整天写成 md(x,y) 的救赎感
        if (i <= mid) {
            modify1(lc(tn), tl, mid, i, m);
        } else {
            modify1(rc(tn), mid+1, tr, i, m);
        }
        
        pushup(tn);
    }

    T query1(int tn, int tl, int tr, int i) {
        if (tl == tr) {
            return a[tn];
        }

        pushdown(tn);

        int mid = md(tl, tr);
        if (i <= mid) {
            return query1(lc(tn), tl, mid, i);
        } else {
            return query1(rc(tn), mid+1, tr, i);
        }
    }

    // === 区间操作 ===
    void modify2(int tn, int tl, int tr, int x, int y, MODIFY m) {
        if (y < tl || tr < x) {
            return;
        }

        if (x <= tl && tr <= y) {
            MODIFY a[tn] with m;
            MODIFY lz[tn] with m;
            return;
        }

        pushdown(tn);
        
        int mid = md(tl, tr);
        modify2(lc(tn), tl, mid, x, y, m);
        modify2(rc(tn), mid+1, tr, x, y, m);
        
        pushup(tn);
    }

    T query2(int tn, int tl, int tr, int x, int y) {
        if (y < tl || tr < x) {
            return O;
        }

        if (x <= tl && tr <= y) {
            return a[tn];
        }

        pushdown(tn);
        
        int mid = md(tl, tr);
        return (
            query2(lc(tn), tl, mid, x, y, m)
          ⊕ query2(rc(tn), mid+1, tr, x, y, m)
        )；
    }
} sgt;

总结：

  • 细分操作前 pushdown；
  • 细分修改后 pushup；
  • 区间操作特判包含/不交；
  • 单点操作特判区间缩成点。
  • 以及，md(x,y) 打得太顺手了……

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)