线段树小记

Aelt · 2025-10-08 11:57:07 · 算法·理论

如题

线段树是一个二叉搜索树，可以将 O(n) 的扫变成 O(log n)，适用范围很广，可以在线维护修改以及查询区间上的最值，求和。

常看这个

习惯写 pushup：

求区间和的

void pushup(int t) {
    sum[t] = sum[t << 1] + sum[t << 1 | 1];
}

然后是 pushnow：

void pushnow(int t, int l, int r, int v) {
    sum[t] += (r - l + 1) * v;
    tag[t] += v;
}

tag 是懒标记，先把 sum 加上该加的，就是子树的和，然后打上懒标记，方便之后往下传。

最后是 pushdown，即往下传懒标记：

void pushdown(int t, int l, int r) {
    if (!tag[t]) return; // 如果没有懒标记就返回
    int mid = (l + r) >> 1;
    pushnow(t << 1, l, mid, tag[t]);
    pushnow(t << 1 | 1, mid + 1, r, tag[t]);
    tag[t] = 0; // 往子树传完后把自己的懒标记删掉
}

建树：

void build(int t, int l, int r) {
    if (l == r) {
        sum[t] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(t << 1, l, mid);
    build(t << 1 | 1, mid + 1, r);
    pushup(t);
}

区间修改：

void modify(int t, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        pushnow(t, l, r, v);
        return;
    }
    pushdown(t, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(t << 1, l, mid, ql, qr, v);
    if (qr > mid) modify(t << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(t);
}

区间查询：

int query(int t, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[t];
    pushdown(t, l, r);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res += query(t << 1, l, mid, ql, qr);
    if (qr > mid) res += query(t << 1 | 1, mid + 1, r, ql, qr);
    pushup(t);
    return res; 
}

然后就可以解决线段树 1 这道题。