查看源代码：
segment-tree-template.md

---
title: 线段树板子
createTime: 2025/11/23
categories:
    - IT
tags:
    - OI
---

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

```cpp
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)` 打得太顺手了……** {style="color:red;"}