线段树CSP-S

💡 核心思想

线段树是一种平衡二叉树，每个节点表示一个区间。支持 $O(\log n)$ 的区间修改和区间查询。通过懒标记（Lazy Tag）技术，可以高效处理区间操作，是竞赛中最重要的数据结构之一。

🎯 直觉理解

线段树就像一个公司的管理架构：CEO管全公司，下面两个VP各管一半，每个VP下面又有两个经理各管四分之一……修改一个人的信息只需要更新从它到CEO路径上的 $\log n$ 个节点。查一个部门的总和只需要合并若干个"恰好覆盖"的子部门数据。

📝 算法流程

1. 建树：递归构建，叶子节点存原值，非叶子存子节点合并值
2. 单点/区间修改：递归到目标区间，更新+打标记
3. 查询：递归合并覆盖查询区间的节点
4. 懒标记：修改时延迟更新子树

$$\text{线段树空间：开 } 4n \text{ 大小}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
ll a[N], tree[4*N], lazy[4*N];
void pushup(int p) { tree[p] = tree[p*2] + tree[p*2+1]; }
void pushdown(int p, int l, int r) {
    if (lazy[p]) {
        int mid = (l+r)/2;
        tree[p*2] += lazy[p]*(mid-l+1); lazy[p*2] += lazy[p];
        tree[p*2+1] += lazy[p]*(r-mid); lazy[p*2+1] += lazy[p];
        lazy[p] = 0;
    }
}
void build(int p, int l, int r) {
    if (l == r) { tree[p] = a[l]; return; }
    int mid = (l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r);
    pushup(p);
}
void update(int p, int l, int r, int ql, int qr, ll v) {
    if (ql<=l && r<=qr) { tree[p]+=v*(r-l+1); lazy[p]+=v; return; }
    pushdown(p,l,r); int mid=(l+r)/2;
    if (ql<=mid) update(p*2,l,mid,ql,qr,v);
    if (qr>mid) update(p*2+1,mid+1,r,ql,qr,v);
    pushup(p);
}
ll query(int p, int l, int r, int ql, int qr) {
    if (ql<=l && r<=qr) return tree[p];
    pushdown(p,l,r); int mid=(l+r)/2; ll ans=0;
    if (ql<=mid) ans+=query(p*2,l,mid,ql,qr);
    if (qr>mid) ans+=query(p*2+1,mid+1,r,ql,qr);
    return ans;
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    while (m--) {
        int op; cin >> op;
        if (op==1) { int l,r; ll v; cin>>l>>r>>v; update(1,1,n,l,r,v); }
        else { int l,r; cin>>l>>r; cout<<query(1,1,n,l,r)<<"\n"; }
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目