罗罗编程学习记录
本页内容 展开查看

02.11.1 线段树与树状数组

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.11 高级数据结构

覆盖范围

  • 线段树区间查询/区间更新与懒标记
  • 树状数组区间查询与区间修改
  • 二维线段树/树状数组
  • 线段树动态开点

高频题速览

编号 题目 难度 频率
02.11.1-001 线段树区间求和点修改 基础 ★★★★
02.11.1-002 线段树区间更新懒标记 高级 ★★★★
02.11.1-003 树状数组区间查询 基础 ★★★★
02.11.1-004 树状数组区间修改区间查询 进阶 ★★★
02.11.1-005 线段树 vs 树状数组对比 基础 ★★★★
02.11.1-006 懒标记下推顺序 高级 ★★★
02.11.1-007 线段树动态开点 进阶 ★★★
02.11.1-008 二维树状数组 进阶 ★★★

02.11.1-001 线段树区间求和点修改

频率 ★★★★ | 难度 基础

一句话结论

线段树用数组表示完全二叉树,每个节点存对应区间的和;点修改时更新叶子节点并向上更新父节点;区间查询时把区间拆成 O(log n) 个节点求和。

概念解释

  • 树高:O(log n)。
  • 数组表示:节点 i 的左右子节点为 2i 和 2i+1。
  • 点修改:O(log n)。
  • 区间查询:O(log n)。

原理流程

  1. 建树:叶子节点存原始值,父节点存两子节点和。
  2. 点修改:找到叶子节点,更新值,向上更新父节点。
  3. 区间查询:递归查询,当前节点区间完全包含则返回,否则拆分查询。

代码 / 示例

class SegmentTree {
    private final int[] tree;
    private final int n;

    SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        build(nums, 1, 0, n - 1);
    }
    private void build(int[] nums, int node, int l, int r) {
        if (l == r) { tree[node] = nums[l]; return; }
        int mid = (l + r) / 2;
        build(nums, 2 * node, l, mid);
        build(nums, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    void update(int pos, int val) { update(1, 0, n - 1, pos, val); }
    private void update(int node, int l, int r, int pos, int val) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2 * node, l, mid, pos, val);
        else update(2 * node + 1, mid + 1, r, pos, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    int query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }
    private int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
}

常见误区

  • 误区:数组大小 2n;正解:线段树数组大小通常 4n(非完全二叉树时可能超)。
  • 误区:update 只改叶子;正解:改叶子后要向上更新所有父节点。

追问 / 延伸

  • Q:线段树空间? A:4n,最坏情况。
  • Q:线段树 vs 前缀和? A:前缀和 O(1) 查询但 O(n) 更新;线段树 O(log n) 查询和 O(log n) 更新。

02.11.1-002 线段树区间更新懒标记

频率 ★★★★ | 难度 高级

一句话结论

区间更新时不立即下推到子节点,而是在节点上打一个懒标记(lazy tag)表示"该节点区间已被整体加 val";查询/下次更新时若需要访问子节点,先把懒标记下推到子节点。

概念解释

  • 懒标记:节点上存的待下推增量。
  • 下推:把父节点懒标记加到子节点值和子节点懒标记上,然后清父节点懒标记。
  • 区间更新:O(log n),因为只拆成 O(log n) 个节点打标记。

原理流程

  1. 区间更新:当前节点区间完全包含在更新区间内,直接改节点值并打懒标记,返回。
  2. 否则先下推懒标记,再递归更新子节点,最后更新父节点值。
  3. 区间查询:同上,需要访问子节点时先下推。

代码 / 示例

class LazySegTree {
    private final int[] tree, lazy;
    private final int n;

    LazySegTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n]; lazy = new int[4 * n];
        build(nums, 1, 0, n - 1);
    }
    private void build(int[] nums, int node, int l, int r) {
        if (l == r) { tree[node] = nums[l]; return; }
        int mid = (l + r) / 2;
        build(nums, 2 * node, l, mid);
        build(nums, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    private void pushDown(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        tree[2 * node] += lazy[node] * (mid - l + 1);
        lazy[2 * node] += lazy[node];
        tree[2 * node + 1] += lazy[node] * (r - mid);
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
    void update(int ql, int qr, int val) { update(1, 0, n - 1, ql, qr, val); }
    private void update(int node, int l, int r, int ql, int qr, int val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node] += val * (r - l + 1);
            lazy[node] += val;
            return;
        }
        pushDown(node, l, r);
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ql, qr, val);
        update(2 * node + 1, mid + 1, r, ql, qr, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    int query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }
    private int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        pushDown(node, l, r);
        int mid = (l + r) / 2;
        return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
}

常见误区

  • 误区:下推时只改子节点值不改子节点懒标记;正解:子节点懒标记也要累加,否则下次下推丢失。
  • 误区:区间更新时立即递归到叶子;正解:完全包含则打标记返回,不递归。

追问 / 延伸

  • Q:懒标记下推顺序? A:先下推再递归子节点,最后更新父节点。
  • Q:懒标记支持区间赋值吗? A:支持,但赋值标记要覆盖累加标记,需要区分两种标记。

02.11.1-003 树状数组区间查询

频率 ★★★★ | 难度 基础

一句话结论

树状数组用 c[i] 维护 (i - lowbit(i), i] 的和;点修改 add(i, val) 向上更新所有包含 i 的 c;区间查询 prefix(i) 求和 (0, i],区间和 = prefix(r) - prefix(l-1)。

概念解释

  • lowbit(i):i 二进制最低位 1 对应的值,如 lowbit(6)=2。
  • c[i]:维护区间 (i-lowbit(i), i]。
  • add(i, val):i += lowbit(i) 向上更新。
  • prefix(i):i -= lowbit(i) 向下求和。

原理流程

  1. add(i, val):c[i] += val,i += lowbit(i),重复。
  2. prefix(i):sum += c[i],i -= lowbit(i),直到 i==0。
  3. 区间和 [l,r] = prefix(r) - prefix(l-1)。

代码 / 示例

class BIT {
    private final int[] c;
    private final int n;
    BIT(int n) { this.n = n; c = new int[n + 1]; }
    int lowbit(int x) { return x & (-x); }
    void add(int i, int val) {
        while (i <= n) { c[i] += val; i += lowbit(i); }
    }
    int prefix(int i) {
        int sum = 0;
        while (i > 0) { sum += c[i]; i -= lowbit(i); }
        return sum;
    }
    int query(int l, int r) { return prefix(r) - prefix(l - 1); }
}

常见误区

  • 误区:树状数组下标从 0 开始;正解:从 1 开始,lowbit(0)=0 会死循环。
  • 误区:add 时 i 超过 n;正解:循环条件 i <= n。

追问 / 延伸

  • Q:树状数组 vs 线段树? A:树状数组代码短、空间小(n),但功能有限(区间和、单点修改);线段树功能强(区间和、区间更新、最大值等)但代码长。
  • Q:lowbit 怎么算? A:x & (-x),补码性质。

02.11.1-004 树状数组区间修改区间查询

频率 ★★★ | 难度 进阶

一句话结论

用两个树状数组 B1、B2;区间加 val 在 [l,r]:add(B1, l, val)、add(B1, r+1, -val)、add(B2, l, val*(l-1))、add(B2, r+1, -val*r);prefix(i) = prefix(B1, i)*i - prefix(B2, i)。

概念解释

  • 差分数组:区间加转化为两点加。
  • 两个 BIT:B1 维护差分,B2 维护差分*i 的加权和。
  • 公式:prefix(i) = sum(B1, i)*i - sum(B2, i)。

原理流程

  1. 区间 [l,r] 加 val:差分 d[l]+=val, d[r+1]-=val。
  2. prefix(i) = sum_{k=1}^{i} d[k] * (i - k + 1) = isum(d) - sum(d(k-1))。
  3. 用 B1 维护 d,B2 维护 d*(k-1)。

代码 / 示例

class BIT2D {
    private final int[] B1, B2;
    private final int n;
    BIT2D(int n) { this.n = n; B1 = new int[n + 1]; B2 = new int[n + 1]; }
    int lowbit(int x) { return x & (-x); }
    void add(int[] c, int i, int val) { while (i <= n) { c[i] += val; i += lowbit(i); } }
    int prefix(int[] c, int i) { int s = 0; while (i > 0) { s += c[i]; i -= lowbit(i); } return s; }
    void rangeAdd(int l, int r, int val) {
        add(B1, l, val); add(B1, r + 1, -val);
        add(B2, l, val * (l - 1)); add(B2, r + 1, -val * r);
    }
    int prefix(int i) { return prefix(B1, i) * i - prefix(B2, i); }
    int rangeQuery(int l, int r) { return prefix(r) - prefix(l - 1); }
}

常见误区

  • 误区:区间修改区间查询只用一个 BIT;正解:需要两个 BIT,公式推导见原理。
  • 误区:B2 加权系数写错;正解:B2 维护 d[k](k-1),r+1 处加 -valr。

追问 / 延伸

  • Q:公式怎么推? A:prefix(i) = sum_{k=1}^{i} d[k](i-k+1) = isum(d) - sum(d*(k-1))。
  • Q:树状数组支持区间最大值吗? A:普通树状数组不支持,需要线段树或特殊结构。

02.11.1-005 线段树 vs 树状数组对比

频率 ★★★★ | 难度 基础

一句话结论

树状数组代码短、空间小(n),但只支持区间和与单点修改(或区间修改区间和);线段树代码长、空间大(4n),但支持区间和、区间更新、区间最大值、区间最值等各种操作。

概念解释

  • 树状数组:lowbit 思想,O(log n)。
  • 线段树:二叉树,每个节点存区间信息,O(log n)。
  • 选型:区间和问题用树状数组,区间最值或复杂操作用电线段树。

原理流程

  1. 区间和 + 单点修改:树状数组。
  2. 区间和 + 区间修改:树状数组(两个 BIT)或线段树(懒标记)。
  3. 区间最大值/最小值:线段树。
  4. 二维区间和:二维树状数组或二维线段树。

代码 / 图示

特性       树状数组        线段树
代码长度   短             长
空间       n              4n
区间和     支持           支持
区间修改   支持(两个BIT) 支持(懒标记)
区间最值   不支持         支持
二维扩展   容易           复杂

常见误区

  • 误区:树状数组能做区间最大值;正解:普通树状数组不能,需要线段树。
  • 误区:线段树空间 2n;正解:通常 4n。

追问 / 延伸

  • Q:竞赛中用哪个? A:简单区间和用树状数组,复杂操作用线段树。
  • Q:工程中用哪个? A:工程中线段树用得少,通常用数据库或缓存。

02.11.1-006 懒标记下推顺序

频率 ★★★ | 难度 高级

一句话结论

在递归更新或查询时,必须先 pushDown 当前节点的懒标记,再递归访问子节点;递归返回后再用子节点值更新当前节点值;顺序错误会导致子节点数据不一致。

概念解释

  • 下推时机:需要访问子节点之前。
  • 下推操作:把懒标记加到子节点值和子节点懒标记上。
  • 更新顺序:下推 -> 递归子节点 -> 更新父节点值。

原理流程

  1. 当前节点区间完全包含:打懒标记返回。
  2. 否则:先 pushDown,再递归子节点,最后 tree[node] = 左子 + 右子。
  3. 查询同理:pushDown 后再递归。

代码 / 图示

错误顺序:
  递归子节点 -> pushDown -> 更新父节点
  (子节点数据未下推,查询结果错误)

正确顺序:
  pushDown -> 递归子节点 -> 更新父节点

常见误区

  • 误区:下推后不更新父节点值;正解:子节点更新后父节点值也要更新。
  • 误区:叶子节点下推;正解:叶子节点没有子节点,不需要下推。

追问 / 延伸

  • Q:区间赋值标记怎么下推? A:赋值标记覆盖累加标记,下推时先看是否有赋值标记,有则覆盖。
  • Q:懒标记可以合并吗? A:可以,连续累加直接加在懒标记上。

02.11.1-007 线段树动态开点

频率 ★★★ | 难度 进阶

一句话结论

普通线段树预分配 4n 数组,动态开点只在需要时才创建节点(用指针或 map 存节点);适合值域很大(如 1e9)但实际操作点少的场景。

概念解释

  • 普通线段树:预分配 4n 数组,n 大时空间不够。
  • 动态开点:用 Node 类或 map,只创建访问过的节点。
  • 值域大:如区间 [1, 1e9],但只有 O(q) 个操作点。

原理流程

  1. 节点类:left、right、val、lazy。
  2. update/query 时:如果左子节点不存在且需要访问,则创建左子节点。
  3. 空间复杂度 O(q log n),q 为操作数。

代码 / 示例

class DynSegTree {
    static class Node {
        long val; long lazy;
        Node left, right;
    }
    private final Node root = new Node();
    private final int n;
    DynSegTree(int n) { this.n = n; }

    void update(Node node, int l, int r, int ql, int qr, long val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { node.val += val * (r - l + 1); node.lazy += val; return; }
        int mid = (l + r) / 2;
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        pushDown(node, l, r);
        update(node.left, l, mid, ql, qr, val);
        update(node.right, mid + 1, r, ql, qr, val);
        node.val = node.left.val + node.right.val;
    }
    private void pushDown(Node node, int l, int r) {
        if (node.lazy == 0) return;
        int mid = (l + r) / 2;
        node.left.val += node.lazy * (mid - l + 1);
        node.left.lazy += node.lazy;
        node.right.val += node.lazy * (r - mid);
        node.right.lazy += node.lazy;
        node.lazy = 0;
    }
}

常见误区

  • 误区:动态开点预分配所有节点;正解:按需创建,空间 O(q log n)。
  • 误区:下推时不创建子节点;正解:需要访问子节点时才创建。

追问 / 延伸

  • Q:动态开点 vs 离散化? A:值域大但操作点少时,动态开点或离散化都可以;离散化需要离线。
  • Q:动态开点空间? A:O(q log n),q 为操作数,log n 为树高。

02.11.1-008 二维树状数组

频率 ★★★ | 难度 进阶

一句话结论

一维树状数组扩展到二维:c[i][j] 维护矩形区域 (i-lowbit(i), i] × (j-lowbit(j), j] 的和;点修改遍历 i 维度和 j 维度;区间查询 = 四个角前缀和容斥。

概念解释

  • 二维 BIT:c[i][j] 维护一个矩形区域。
  • 点修改:i += lowbit(i), j += lowbit(j) 双重循环。
  • 二维前缀和:sum(x,y) = 矩形 (1,1) 到 (x,y) 的和。
  • 二维区间和:容斥,sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1)。

原理流程

  1. add(i, j, val):外层 i += lowbit(i),内层 j += lowbit(j)。
  2. prefix(i, j):外层 i -= lowbit(i),内层 j -= lowbit(j),累加 c[i][j]。
  3. 矩形和 [x1,x2]×[y1,y2]:容斥公式。

代码 / 示例

class BIT2D {
    private final int[][] c;
    private final int n, m;
    BIT2D(int n, int m) { this.n = n; this.m = m; c = new int[n + 1][m + 1]; }
    int lowbit(int x) { return x & (-x); }
    void add(int i, int j, int val) {
        for (int x = i; x <= n; x += lowbit(x))
            for (int y = j; y <= m; y += lowbit(y))
                c[x][y] += val;
    }
    int prefix(int i, int j) {
        int sum = 0;
        for (int x = i; x > 0; x -= lowbit(x))
            for (int y = j; y > 0; y -= lowbit(y))
                sum += c[x][y];
        return sum;
    }
    int rectQuery(int x1, int y1, int x2, int y2) {
        return prefix(x2, y2) - prefix(x1 - 1, y2) - prefix(x2, y1 - 1) + prefix(x1 - 1, y1 - 1);
    }
}

常见误区

  • 误区:二维区间和不用容斥;正解:必须用四个角容斥。
  • 误区:add 时只改一维;正解:两维都要遍历。

追问 / 延伸

  • Q:二维树状数组空间? A:O(n*m),n、m 为两维大小。
  • Q:二维线段树? A:可以嵌套,空间 O(n*m),但动态开点更省。

待整理清单

  • [ ] 线段树区间最大值
  • [ ] 线段树合并
  • [ ] 二维线段树动态开点