进阶算法1: 线段树

线段树

原理介绍

线段树 是一种基于分治思想的二叉树数据结构，用于高效处理区间修改和区间查询问题。它将一个长度为 $n$ 的数组划分为若干个线段，每个节点代表一段区间的聚合信息（如和、最值等）。

核心思想

1. 建树(build)：将整个数组递归地一分为二，直到每个叶子节点只包含一个元素。每个节点的值由其左右子节点合并得到。
2. 懒标记的pushup和pushdown：当一次区间修改完全覆盖某个节点时，不继续向下更新子节点，而是打上一个”懒标记”，等将来需要访问其子节点时再下传（push 操作）。这样可将区间修改的复杂度从 $O(n)$ 降至 $O(\log n)$。
3. 查询：同样递归进行，若当前节点完全在查询区间内，直接返回其存储的值；若与查询区间无交集，直接返回 0；否则继续向下递归并合并左右结果。

时间复杂度

• 建树：O(n)
• 单次区间修改/查询：O(\log n)
• 空间：O(4n)（通常开原数组大小的 4 倍）

适用场景

• 区间加减、乘除
• 区间求和、最值、GCD
• 区间染色、覆盖问题
• 更复杂的双 lazy 标记（先乘后加等）

---

以下附上代码：

#include <bits/stdc++.h>
#define mid (start + end) / 2
#define lc node * 2
#define rc node * 2 + 1
using namespace std;
typedef long long ll;

const int maxn = 100005;
ll tree[maxn * 4], lazy[maxn * 4];
vector<ll> ls;
ll n, m, choice;

//下传懒标记
void push(ll node, ll start, ll end) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node] * (end - start + 1);
        if (start != end) {
            lazy[lc] += lazy[node];
            lazy[rc] += lazy[node];
        }
        lazy[node] = 0;
    }
}

// 建树
void build(ll node, ll start, ll end) {
    if (start == end)
        tree[node] = ls[start];
    else {
        build(lc, start, mid);
        build(rc, mid + 1, end);
        tree[node] = tree[lc] + tree[rc];
    }
}

// 区间加法
void add(ll node, ll start, ll end, ll l, ll r, ll k) {
    push(node, start, end);
    if (start > r || end < l) return;                 // 完全无交集
    if (l <= start && end <= r) {                     // 完全覆盖
        lazy[node] += k;
        push(node, start, end);
        return;
    }
    add(lc, start, mid, l, r, k);
    add(rc, mid + 1, end, l, r, k);
    tree[node] = tree[lc] + tree[rc];
}

// 区间求和
ll sum(ll node, ll start, ll end, ll l, ll r) {
    if (start > r || end < l) return 0;               // 完全无交集
    push(node, start, end);
    if (l <= start && end <= r) return tree[node];    // 完全覆盖
    ll la = sum(lc, start, mid, l, r);
    ll ra = sum(rc, mid + 1, end, l, r);
    return la + ra;
}

int main() {
    cin >> n >> m;
    ls.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> ls[i];
    build(1, 1, n);

    ll x, y, k;
    for (int i = 0; i < m; i++) {
        cin >> choice;
        if (choice == 1) {
            cin >> x >> y >> k;
            add(1, 1, n, x, y, k);
        } else {
            cin >> x >> y;
            cout << sum(1, 1, n, x, y) << '\n';
        }
    }
    return 0;
}