代码模板-线段树

线段树用完全二叉树的数组存储，节点 p 的左右儿子为 p<<1 和 p<<1|1，开 4 倍空间。每个节点维护一个区间的信息，建树/修改/查询都在 $O(\log n)$ 的一条树链上完成。

单点修改 + 区间查询（维护区间最大值）

#define lc(p) ((p)<<1)
#define rc(p) ((p)<<1|1)

const int N = 2e5 + 5;
int a[N];
struct node {
    int l, r, val;        // 维护区间 [l,r] 的信息
} t[4 * N];

void push_up(int p) {     // 向上合并信息
    t[p].val = max(t[lc(p)].val, t[rc(p)].val);
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].val = a[l]; return; }  // 叶子：按题意取初值
    int mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    push_up(p);
}

void change(int p, int id, int x) {           // 单点修改：a[id] = x
    if (t[p].l == t[p].r) { t[p].val = x; return; }
    int mid = (t[p].l + t[p].r) >> 1;
    if (id <= mid) change(lc(p), id, x);
    else change(rc(p), id, x);
    push_up(p);
}

int query(int p, int l, int r) {              // 区间查询 [l,r]
    if (l <= t[p].l && t[p].r <= r) return t[p].val;
    int mid = (t[p].l + t[p].r) >> 1, ans = 0;
    if (l <= mid) ans = query(lc(p), l, r);
    if (r > mid) ans = max(ans, query(rc(p), l, r));
    return ans;
}

区间修改 + 区间查询（lazy tag，维护区间和）

区间修改借助懒标记（lazy tag）：在完全包含的节点上打标记后直接返回，下次修改/查询经过其子节点时再 push_down 下传，保证 $O(\log n)$。

#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)

const int N = 1e5 + 5;
int a[N], n;
struct node {
    int l, r, v, add;     // v: 区间和; add: 懒标记
} t[4 * N];

void push_up(int p) {
    t[p].v = t[lc(p)].v + t[rc(p)].v;
}

void push_down(int p) {                       // 懒标记下传
    if (t[p].add) {
        t[lc(p)].add += t[p].add;
        t[lc(p)].v += t[p].add * (t[lc(p)].r - t[lc(p)].l + 1);
        t[rc(p)].add += t[p].add;
        t[rc(p)].v += t[p].add * (t[rc(p)].r - t[rc(p)].l + 1);
        t[p].add = 0;
    }
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].v = a[l]; return; }
    int mid = (l + r) / 2;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    push_up(p);
}

void change(int p, int l, int r, int k) {     // 区间修改：a[l..r] += k
    if (l <= t[p].l && t[p].r <= r) {
        t[p].add += k;
        t[p].v += (t[p].r - t[p].l + 1) * k;
        return;
    }
    push_down(p);
    int mid = (t[p].l + t[p].r) / 2;
    if (l <= mid) change(lc(p), l, r, k);
    if (mid < r) change(rc(p), l, r, k);
    push_up(p);
}

int query(int p, int l, int r) {              // 区间查询：sum(a[l..r])
    if (l <= t[p].l && t[p].r <= r) return t[p].v;
    push_down(p);
    int mid = (t[p].l + t[p].r) / 2, ans = 0;
    if (l <= mid) ans += query(lc(p), l, r);
    if (mid < r) ans += query(rc(p), l, r);
    return ans;
}

相关笔记：【数据结构】线段树（一）学习笔记