绝大多数实际场景下，用数组实现线段树更合适，因其结构固定、缓存友好、不易出错且支持快速初始化；需开4×n大小、下标从1开始，并配合懒标记优化区间修改。

线段树用数组还是指针实现更合适

绝大多数实际场景下，用 vector 或普通数组实现线段树比动态指针树更优。原因很实在：指针版写起来容易出错（内存泄漏、空指针解引用）、缓存不友好、常数大；而数组版结构固定、下标规则明确（tree[i] 的左右子节点是 tree[2*i] 和 tree[2*i+1]），且支持批量初始化和快速重置。

注意点：

• 数组大小至少要开到 4 * n，不能只开 2*n —— 否则在非 2 的幂长度时会越界
• 下标从 1 开始用（即 tree[1] 是根）比从 0 开始逻辑更干净，避免父子下标公式里反复加减 1
• 如果数据范围可能达 1e5，别用 int tree[200005] 这种栈上静态数组，改用 vector tree

区间修改必须用懒标记（lazy tag）吗

不是“必须”，但不用就大概率超时或写错。比如对长度为 1e5 的数组做 1e4 次区间加法，暴力更新每个叶子节点，最坏 O(n) × O(q) = 1e9，稳 TLE。

懒标记本质是延迟传播：只在真正需要访问子区间时才把父节点的未处理操作推下去。关键操作有三个：

立即学习“C++免费学习笔记（深入）”；

• push_down(idx, l, r)：把 lazy[idx] 加到左右子节点的 lazy 上，并更新 tree[idx] 值，最后清空 lazy[idx]
• 所有 update 和 query 进入子区间前，必须先调用 push_down
• lazy 数组类型要和操作匹配：区间加对应 long long lazy[]，区间赋值则需额外标记是否“已赋值”

build、update、query 的递归边界怎么写才不出错

核心原则：递归函数的参数统一为 (idx, l, r, ql, qr, val) 形式，其中 [l, r] 是当前节点覆盖区间，[ql, qr] 是目标操作区间。边界判断只依赖这四个变量，不引入额外标志位。

常见错误写法：if (l == r) { tree[idx] = a[l]; return; } —— 这只适用于 build，混进 update 就崩了。

正确写法要点：

• build(idx, l, r)：当 l == r 时直接赋值 a[l]；否则递归建左右子树，再 tree[idx] = tree[2*idx] + tree[2*idx+1]
• update(idx, l, r, ql, qr, val)：若 qr 直接返回；若 ql ，更新当前节点并设 lazy[idx] += val，然后 return；否则先 push_down，再递归左右
• query(idx, l, r, ql, qr)：同样先判无交集 / 完全包含；否则 push_down 后左右递归求和

单点修改和区间修改能共用同一套 update 函数吗

能，而且应该共用。单点修改只是区间修改的特例：令 ql == qr 即可。强行拆成两个函数会导致重复逻辑、维护成本高、容易漏修 bug。

实操建议：

• 把 update 接口设计为 void update(int ql, int qr, long long val)，内部调用私有递归函数
• 如果业务中存在“单点赋值”和“区间加”两种语义，不要重载函数名，而是加一个枚举参数 OpType，并在 push_down 和合并逻辑里区分处理
• 测试时务必覆盖三种 case：单点（1,1）、跨中点（1,n/2+1）、完全左偏（1,10）—— 很多 bug 只在特定区间形状下暴露

class SegmentTree {
    int n;
    vector tree, lazy;
    void push_down(int idx, int l, int r) {
        if (lazy[idx] == 0) return;
        tree[idx] += lazy[idx] * (r - l + 1);
        if (l != r) {
            lazy[idx * 2] += lazy[idx];
            lazy[idx * 2 + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
    void update(int idx, int l, int r, int ql, int qr, long long val) {
        push_down(idx, l, r);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[idx] += val;
            push_down(idx, l, r); // 立即生效，保证 tree[idx] 正确
            return;
        }
        int mid = (l + r) / 2;
        update(idx * 2, l, mid, ql, qr, val);
        update(idx * 2 + 1, mid + 1, r, ql, qr, val);
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }
public:
    SegmentTree(int size, const vector& a) : n(size), tree(4 * n), lazy(4 * n) {
        function build = [&](int idx, int l, int r) {
            if (l == r) {
                tree[idx] = a[l];
                return;
            }
            int mid = (l + r) / 2;
            build(idx * 2, l, mid);
            build(idx * 2 + 1, mid + 1, r);
            tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
        };
        build(1, 0, n - 1);
    }
    void update(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
    long long query(int l, int r) {
        // query 实现类似 update，此处省略
        return 0;
    }
};

数组大小、懒标记传播时机、递归入口的区间闭合性——这三个地方出错，调试起来最费时间。