线段树NOIP

💡 核心思想

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

🎯 直觉理解

线段树是"把数组区间拆成树节点来管理"的结构：每个节点管一段区间，父节点 = 两个儿子的合并。单点/区间修改和查询都是 $O(log n)$。

懒标记（lazy）是区间修改的关键：给整段打标记"这段要加 v"，先不改子节点，等真的需要访问子节点时才把标记下传——这样区间修改不用递归到底。

线段树 = 建树 + 查询 + 修改（含下传标记）+ 合并逻辑。先写会"单点改、区间查"的最简版，再学懒标记。合并逻辑决定线段树能维护什么：求和、最值、最大子段和……都是改合并函数。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include 
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<