🌳 线段树从零入门（区间和版本）

学生反馈"线段树我不会"，从零开始讲。先掌握"区间和"版（单量），F 题的 sum/sum2/sum3 只是"升级皮肤"。

---

一、线段树解决什么问题？

反复做两种区间操作（N, M 可达 10⁵）：

查询：区间 [l, r] 的和
修改：区间 [l, r] 每个数 +k（或赋值）

朴素：查询 O(n)、修改 O(n) → 超时。
线段树：两个操作都 O(log n) —— 把数组二分分段，预先算好每段的和，改/查只碰受影响的段。

---

二、结构（核心直觉）

数组 [1, 5, 4, 2, 3]，不断二分：

                    [1..5]=15
                  /          \
            [1..3]=10      [4..5]=5
            /     \         /    \
      [1..2]=6   [3..3]=4 [4..4]=2 [5..5]=3
      /     \
 [1..1]=1 [2..2]=5

规律：

每个节点 = 一个区间，存该区间信息（和）
父亲 = 左孩子 + 右孩子（合并）
叶子 = 单个元素

存储：数组 tree[4*N]，根 = 1，左孩子 = 2p，右孩子 = 2p+1（同堆）。
为什么 4 倍空间：完全二叉树最坏约 2×2^ceil(log2 N) 个节点，4N 安全。

---

三、三个基本操作（区间和版）

1. build —— 建树

void build(int p, int l, int r, vector<int>& a) {
    if (l == r) { tree[p] = a[l]; return; }      // 叶子
    int mid = (l + r) / 2;
    build(p*2, l, mid, a);
    build(p*2+1, mid+1, r, a);
    tree[p] = tree[p*2] + tree[p*2+1];           // 向上合并
}

2. query —— 查询区间和

int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p];      // 完全覆盖：直接返回
    int mid = (l + r) / 2, res = 0;
    if (ql <= mid) res += query(p*2, l, mid, ql, qr);      // 左边有重叠
    if (qr > mid)  res += query(p*2+1, mid+1, r, ql, qr);  // 右边有重叠
    return res;
}

3. update —— 单点修改

void update(int p, int l, int r, int pos, int val) {
    if (l == r) { tree[p] = val; return; }
    int mid = (l + r) / 2;
    if (pos <= mid) update(p*2, l, mid, pos, val);
    else            update(p*2+1, mid+1, r, pos, val);
    tree[p] = tree[p*2] + tree[p*2+1];           // 回溯重算
}

---

四、懒标记（区间修改的关键）

区间修改若真去改每个叶子 → 还是 O(n)。懒标记：改的时候不急着下传，先记一笔"欠账"，等必须用到孩子时再结清。

比喻：给全班发通知，不挨个喊，先在黑板写"明天放假"（懒标记），有人来问细节再详细说。

int lazy[4*N];                                   // 欠孩子的加法

void pushDown(int p, int l, int r) {             // 结账
    if (lazy[p] != 0) {
        int mid = (l + r) / 2;
        lazy[p*2]   += lazy[p];
        tree[p*2]   += lazy[p] * (mid - l + 1);
        lazy[p*2+1] += lazy[p];
        tree[p*2+1] += lazy[p] * (r - mid);
        lazy[p] = 0;
    }
}

void updateRange(int p, int l, int r, int ql, int qr, int k) {
    if (ql <= l && r <= qr) {                    // 完全覆盖：只改这里+记账
        tree[p] += k * (r - l + 1);
        lazy[p] += k;
        return;
    }
    pushDown(p, l, r);                           // 部分重叠：先结账再下走
    int mid = (l + r) / 2;
    if (ql <= mid) updateRange(p*2, l, mid, ql, qr, k);
    if (qr > mid)  updateRange(p*2+1, mid+1, r, ql, qr, k);
    tree[p] = tree[p*2] + tree[p*2+1];           // 重算父亲
}

⚠️ 查询时也要 pushDown（欠账可能影响查询结果）。

---

五、通向 F 题：节点从"一个数"变"三个量"

F 题每个节点存 {sum, sum2, sum3}：

合并：三个量都 = 左 + 右
区间加 k（用旧值二项式展开）：

```
sum ← sum + k·len
sum2 ← sum2 + 2k·sum + k²·len
sum3 ← sum3 + 3k·sum2 + 3k²·sum + k³·len
```

区间赋值 k：sum=k·len, sum2=k²·len, sum3=k³·len
双懒标记：赋值清空加法；赋值后再加 → 加到赋值上；下推顺序先 set 后 add

结构完全一样，只是"节点存什么"和"怎么合并/更新"变了。

---

六、作业（先做这个，别直接跳 F 题）

写一个支持以下操作的线段树（N=10，自己造数据）：

建树（初始数组随意）
区间加 k
区间查询和

写完贴代码给我 review。自查清单：4 倍空间？pushDown 在 update 和 query 都调了？改完叶子回溯重算父亲了？

---

七、自测题（答上来 = 真懂）

为什么数组要开 4 倍空间？
query 里"完全覆盖"判断 ql <= l && r <= qr 是什么意思？为什么能直接返回？
懒标记为什么能省时间？（对比：不用懒标记会怎样）
单点修改和区间修改，update 后都要做什么共同操作？