线段树（Segment Tree）是处理区间问题的神器。如果你厌倦了 $O(N)$ 的暴力遍历，又觉得前缀和（Prefix Sum）处理不了动态修改，那么线段树就是那个能带你进入 $O(\log N)$ 世界的理想工具。

线段树

线段树就是把一段序列变成一棵二叉树，通过分治的思想，让原本需要扫一遍的操作在对数时间内完成。

线段树 segmentTree 是一个二叉树，每个结点保存数组 nums 在区间 [s,e] 的最小值、最大值或者总和等信息。线段树可以用树也可以用数组（堆式存储）来实现。对于数组实现，假设根结点的下标为 0，如果一个结点在数组的下标为 node，那么它的左子结点下标为 node×2+1，右子结点下标为 node×2+2。

线段树概念

线段树是一种平衡二叉树，它将一个长度为 $N$ 的数组划分为多个区间。每个节点代表一个区间 $[L, R]$：

• 根节点代表整个区间 $[1, N]$。
• 叶子节点代表长度为 1 的元区间 $[i, i]$。
• 内部节点 $[L, R]$ 的左儿子代表 $[L, \text{mid}]$，右儿子代表 $[\text{mid}+1, R]$，其中 $\text{mid} = \lfloor (L+R)/2 \rfloor$。

核心优势：时空复杂度

线段树本质上是将一个区间 $[1, n]$ 递归地对半拆分，直到拆成长度为 1 的叶子节点。每个节点存储该区间的信息（如和、最大值等）。

• 根节点：代表区间 $[1, n]$。
• 子节点：节点 $[L, R]$ 的左孩子代表 $[L, \text{mid}]$，右孩子代表 $[\text{mid}+1, R]$，其中 $\text{mid} = \lfloor (L+R)/2 \rfloor$。

此外还涉及懒惰传播，

核心逻辑：如果当前节点代表的区间被修改区间完全包含，就在该节点打上一个“懒标记”（Lazy Tag），记录下这次修改，而不继续递归更新它的所有子孙。

按需下推（Push Down）：只有当下次需要访问或查询该节点的子节点时，才顺便将标记传下去。这避免了大量不必要的 $O(N)$ 更新。

线段树是将数组划分为一棵平衡二叉树。它是这三者中最强大的，几乎可以处理任何区间相关的问题。

• 核心思想：分治法。根节点管 $[1, n]$，左右孩子各管一半。
• 操作原理：
  • 懒标记 (Lazy Tag)：这是线段树处理区间修改的精髓。当修改整个区间时，先在节点打个“标记”并返回，等到真正访问子节点时再下传。
• 优点：极其通用。不仅能求和，还能处理区间最大值、区间平方和、区间覆盖、甚至区间矩阵乘法。
• 缺点：代码量大，空间开销大（需开 $4n$ 的数组），运行常数比树状数组大。
• 适用场景：复杂的区间操作（如：区间加 + 区间乘 + 区间查询最大值）。

只要一个属性满足“区间加法”（即：你可以通过两个子区间的信息推导出父区间的信息），线段树就能维护它：

• 区间求和：sum = left.sum + right.sum
• 区间最值 (Max/Min)：max = max(left.max, right.max)
• 区间最大公约数 (GCD)：gcd = gcd(left.gcd, right.gcd)
• 区间连续最大子段和：多用于动态规划（GSS系列问题）。
• 甚至区间的矩阵乘法。

线段树的修改操作分为两种：单点修改（Point Update）和区间修改（Range Update）。

由于线段树是一个递归结构，修改的核心逻辑都是：从根节点出发，递归地寻找目标区间，修改后再向上回溯更新父节点。

1. 单点修改 (Point Update)

这是最基础的操作。假设我们要修改数组中第 $i$ 个位置的值。

• 流程：
  1. 从根节点开始。
  2. 如果当前节点是叶子节点且正是我们要找的 $i$，直接修改它。
  3. 如果不是，判断 $i$ 在左半边还是右半边，递归下去。
  4. 关键步骤：在递归返回的过程中，执行 push_up 操作，用更新后的子节点值重新计算当前父节点的值。
• 复杂度：$O(\log n)$，因为只需要走一条从根到叶子的路径。

建树 build 函数

我们在结点 node 保存数组 nums 在区间 [s,e] 的总和。

s=e 时，结点 node 是叶子结点，它保存的值等于 nums[s]。

s<e 时，结点 node 的左子结点保存区间 [s,⌊ (s+e )/2⌋] 的总和，右子结点保存区间 [⌊ (s+e)/2 ⌋+1,e] 的总和，那么结点 node 保存的值等于它的两个子结点保存的值之和。

假设 nums 的大小为 n，我们规定根结点 node=0 保存区间 [0,n−1] 的总和，然后自下而上递归地建树。

单点修改 change 函数

当我们要修改 nums[index] 的值时，我们找到对应区间 [index,index] 的叶子结点，直接修改叶子结点的值为 val，并自下而上递归地更新父结点的值。

范围求和 range 函数

给定区间 [left,right] 时，我们将区间 [left,right] 拆成多个结点对应的区间。

如果结点 node 对应的区间与 [left,right] 相同，可以直接返回该结点的值，即当前区间和。

如果结点 node 对应的区间与 [left,right] 不同，设左子结点对应的区间的右端点为 m，那么将区间 [left,right] 沿点 m 拆成两个区间，分别计算左子结点和右子结点。

从根结点开始递归地拆分区间 [left,right]

2. 区间修改 (Range Update)

如果你要给区间 $[L, R]$ 内的每个数都加 $v$，这就是线段树真正展现威力的时候。这里必须引入我们在第一个问题中提到的懒惰标记 (Lazy Tag)。

• 核心逻辑（三部曲）：

  1. 下推 (Push Down)：如果当前节点有旧的懒标记，先传给儿子，把账结清。
  2. 修改 (Update)：
     • 如果当前节点表示的范围完全包含在目标区间 $[L, R]$ 内，直接更新当前节点值，打上懒标记，然后立即返回（不再往下递归）。
     • 如果没有完全包含，递归左右子树。
  3. 上推 (Push Up)：递归回来后，更新当前节点，确保父节点的数据是准确的

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

  struct Node { long long val; // 存储区间和 long long lazy; // 懒标记 } tree[MAXN * 4]; // 更新父节点信息 void push_up(int node) { tree[node].val = tree[node*2].val + tree[node*2+1].val; } // 下传懒标记 void push_down(int node, int start, int end) { if (tree[node].lazy != 0) { int mid = (start + end) / 2; long long lazy_val = tree[node].lazy; // 更新左儿子 tree[node*2].lazy += lazy_val; tree[node*2].val += lazy_val * (mid - start + 1); // 更新右儿子 tree[node*2+1].lazy += lazy_val; tree[node*2+1].val += lazy_val * (end - mid); // 清除当前节点的标记 tree[node].lazy = 0; } } // 区间修改：将 [L, R] 范围内的数增加 v void update(int node, int start, int end, int L, int R, int v) { // 1. 完全包含：打标记，改值，返回 if (L <= start && end <= R) { tree[node].val += (long long)v * (end - start + 1); tree[node].lazy += v; return; } // 2. 下传旧标记 push_down(node, start, end); int mid = (start + end) / 2; if (L <= mid) update(node*2, start, mid, L, R, v); if (R > mid) update(node*2+1, mid+1, end, L, R, v); // 3. 回溯更新父节点 push_up(node); }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

  #include <vector> using namespace std; class SegmentTree { private: int n; vector<long long> tree; // 存储区间和 vector<long long> lazy; // 存储懒标记 // 向上更新 void pushUp(int k) { tree[k] = tree[k << 1] + tree[k << 1 | 1]; } // 向下推标记 void pushDown(int k, int l, int r) { if (lazy[k] != 0) { int mid = l + (r - l) / 2; // 更新左孩子 lazy[k << 1] += lazy[k]; tree[k << 1] += lazy[k] * (mid - l + 1); // 更新右孩子 lazy[k << 1 | 1] += lazy[k]; tree[k << 1 | 1] += lazy[k] * (r - mid); // 清空当前标记 lazy[k] = 0; } } // 建树 void build(const vector<int>& nums, int k, int l, int r) { if (l == r) { tree[k] = nums[l - 1]; // 注意 nums 是 0 索引 return; } int mid = l + (r - l) / 2; build(nums, k << 1, l, mid); build(nums, k << 1 | 1, mid + 1, r); pushUp(k); } void update(int k, int l, int r, int qL, int qR, int val) { if (qL <= l && r <= qR) { lazy[k] += val; tree[k] += (long long)val * (r - l + 1); return; } pushDown(k, l, r); int mid = l + (r - l) / 2; if (qL <= mid) update(k << 1, l, mid, qL, qR, val); if (qR > mid) update(k << 1 | 1, mid + 1, r, qL, qR, val); pushUp(k); } long long query(int k, int l, int r, int qL, int qR) { if (qL <= l && r <= qR) return tree[k]; pushDown(k, l, r); int mid = l + (r - l) / 2; long long res = 0; if (qL <= mid) res += query(k << 1, l, mid, qL, qR); if (qR > mid) res += query(k << 1 | 1, mid + 1, r, qL, qR); return res; } public: SegmentTree(const vector<int>& nums) { n = nums.size(); tree.assign(4 * n, 0); lazy.assign(4 * n, 0); build(nums, 1, 1, n); } void update(int qL, int qR, int val) { update(1, 1, n, qL, qR, val); } long long query(int qL, int qR) { return query(1, 1, n, qL, qR); } };

  对于一个长度为 $n$ 的区间，线段树是一棵二分树：

  1. 理想情况：如果 $n$ 是 2 的幂，总节点数约为 $2n-1$。

  2. 最坏情况：如果 $n = 2^k + 1$，为了保证最后一层能放下所有的叶子节点，树的高度会增加一层。此时索引地址会跨越到接近 $4n$ 的位置。

     因此，为了防止数组越界，开 4 倍空间是最稳妥的准则。

  pushDown 是为了“去”：你要访问孩子了，所以得把欠孩子的更新给它们。

  pushUp 是为了“回”：孩子更新完了，你作为父亲得汇总最新的状态。

  区间判断逻辑：

  • qL <= mid：说明左孩子管辖的范围里有你需要的部分。
  • qR > mid：说明右孩子管辖的范围里有你需要的部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <vector>

using namespace std;

/**
 * 动态开点线段树（区间加法，区间求和）
 */
struct Node {
    long long val;  // 区间和
    long long add;  // Lazy Tag (懒惰标记)
    int left, right; // 左右孩子在 nodes 数组中的索引

    Node() : val(0), add(0), left(0), right(0) {}
};

class DynamicSegmentTree {
private:
    vector<Node> nodes;
    int root;
    long long L, R; // 树的整体范围，如 [0, 1e9]

    // 创建新节点的辅助函数
    int newNode() {
        nodes.emplace_back();
        return nodes.size() - 1;
    }

    // 向上更新：由孩子节点更新当前节点
    void pushUp(int node) {
        nodes[node].val = nodes[nodes[node].left].val + nodes[nodes[node].right].val;
    }

    // 向下推标记：将当前节点的标记传给孩子
    void pushDown(int node, long long leftRange, long long rightRange) {
        if (!nodes[node].left) nodes[node].left = newNode();
        if (!nodes[node].right) nodes[node].right = newNode();
        
        if (nodes[node].add == 0) return;

        long long mid = leftRange + (rightRange - leftRange) / 2;
        
        // 左孩子更新
        nodes[nodes[node].left].add += nodes[node].add;
        nodes[nodes[node].left].val += nodes[node].add * (mid - leftRange + 1);
        
        // 右孩子更新
        nodes[nodes[node].right].add += nodes[node].add;
        nodes[nodes[node].right].val += nodes[node].add * (rightRange - mid);
        
        // 清空当前标记
        nodes[node].add = 0;
    }

    // 内部递归更新函数
    void update(int& node, long long l, long long r, long long qL, long long qR, int val) {
        if (!node) node = newNode();
        
        // 如果当前区间被完全包含
        if (qL <= l && r <= qR) {
            nodes[node].add += val;
            nodes[node].val += (long long)val * (r - l + 1);
            return;
        }

        pushDown(node, l, r);
        long long mid = l + (r - l) / 2;
        if (qL <= mid) update(nodes[node].left, l, mid, qL, qR, val);
        if (qR > mid) update(nodes[node].right, mid + 1, r, qL, qR, val);
        pushUp(node);
    }

    // 内部递归查询函数
    long long query(int node, long long l, long long r, long long qL, long long qR) {
        if (!node) return 0;
        if (qL <= l && r <= qR) return nodes[node].val;

        pushDown(node, l, r);
        long long mid = l + (r - l) / 2;
        long long res = 0;
        if (qL <= mid) res += query(nodes[node].left, l, mid, qL, qR);
        if (qR > mid) res += query(nodes[node].right, mid + 1, r, qL, qR);
        return res;
    }

public:
    DynamicSegmentTree(long long start, long long end) : L(start), R(end) {
        nodes.emplace_back(); // 占位，让索引从1开始
        root = newNode();
    }

    void update(long long qL, long long qR, int val) {
        update(root, L, R, qL, qR, val);
    }

    long long query(long long qL, long long qR) {
        return query(root, L, R, qL, qR);
    }
};

传统的线段树需要开辟 $4N$ 大小的数组。如果区间范围是 $[0, 10^9]$，数组根本开不下。 动态开点的思路是：按需取用。只有当某个区间被访问或修改时，我们才真正创建这个节点。这样，空间复杂度就从 $O(N)$ 降到了 $O(Q \log N)$（$Q$ 为操作次数），完美解决大范围坐标问题。

[715. Range 模块]：涉及到区间的添加、查询、删除，是动态开点线段树的绝佳舞台。

[732. 我的日程安排表 III]：求区间最大重叠数，也就是线段树维护区间最大值。

A. 树状数组 (BIT) —— 离散化与计数

树状数组最经典的用法不是简单的求和，而是配合离散化来解决逆序对或元素计数问题。

• 307. 区域和检索 - 数组可修改 (Medium)
  • 地位：BIT 的“Hello World”。单点修改，区间求和。
• 315. 计算右侧小于当前元素的个数 (Hard)
  • 核心：从右往左遍历数组，利用 BIT 动态维护“已经出现了哪些数”。这是 BIT 在面试中最常出现的形态。
• 493. 翻转对 (Hard)
  • 核心：在处理 $nums[i] > 2 \times nums[j]$ 时，BIT 配合离散化可以极其优雅地完成计数。

B. 线段树 (Segment Tree) —— 区间更新的艺术

线段树的真正威力在于处理 区间修改（比如：把 $[l, r]$ 全都加 $v$，或者全部变成 $v$）。

• 715. Range 模块 (Hard)
  • 地位：管理实数区间。需要线段树支持区间的添加、查询和删除。
• 699. 掉落的方块 (Hard)
  • 核心：区间高度更新 + 区间最大值查询。这是典型的“动态维护最大值”问题。
• 732. 我的日程安排表 III (Hard)
  • 核心：求区间的最大重叠次数（$k$-次覆盖）。可以使用动态开点线段树。

经典例题

线段树的应用极广，通常只要某种信息满足结合律（即可以通过左右孩子的信息合并得到父节点信息），就能用线段树维护。

「线段树求解最长公共上升子序列问题」的 pushUp 操作。

线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」

307. 区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

1. 其中一类查询要求 更新 数组 nums 下标对应的值
2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 用整数数组 nums 初始化对象
• void update(int index, int val) 将 nums[index] 的值 更新 为 val
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

最大子数组之和也可以使用线段树分治解法

树状数组

树状数组是一种可以动态维护序列前缀和的数据结构（序列下标从 1 开始），它的功能是：

单点修改 add(index,val)：把序列第 index 个数增加 val；

区间查询 prefixSum(index)：查询前 index 个元素的前缀和。

树状数组是一种极其精巧的结构，利用二进制分解来维护区间信息。它在“单点修改”和“前缀和查询”之间达到了完美的平衡。

• 核心思想：利用 lowbit(x) = x & -x 将数组划分为多个 $2^k$ 长度的块。
• 操作原理：
  • 单点修改：向上进位（x += lowbit(x)），更新所有包含该点的管辖区间。
  • 前缀查询：向左下跳（x -= lowbit(x)），拼凑出 $[1, x]$ 的总和。
• 优点：代码极短（核心仅几行），空间开销最小（$O(n)$），常数极小（运行速度极快）。
• 缺点：功能相对局限，主要用于求和、最值等满足结合律且容易求逆的操作，难以原生支持复杂的区间修改（如区间乘法）。
• 适用场景：动态维护前缀和、逆序对计算、单点修改+区间查询

概念

树状数组（Binary Indexed Tree, BIT），又称 Fenwick Tree，是一种极其精巧的数据结构。它主要用于高效地处理区间前缀和的查询与单点值的修改。

树状数组的本质是利用数字的二进制分解来决定每个节点管理的区间范围。

• 线段树是将区间平分成两半。
• 树状数组是将区间 $[1, n]$ 拆分为若干个长度为 $2^k$ 的子区间。

例如，查询前缀和 $S[13]$：

$13$ 的二进制是 $(1101)_2$。它可以拆解为：

$13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1$

对应的区间就是：$(0, 8] + (8, 12] + (12, 13]$。树状数组的每个位置正好存储了这些特定长度区间的和。

灵魂函数：lowbit

树状数组最神奇的地方在于它如何寻找“父亲”和“儿子”。这全靠 lowbit 操作：

这个操作会返回 $x$ 二进制表示中最低位的 1 及其后面的 0。例如：

• $\text{lowbit}(6)$：$6$ 是 $(110)_2$，返回 $(010)_2 = 2$。
• $\text{lowbit}(8)$：$8$ 是 $(1000)_2$，返回 $(1000)_2 = 8$。

lowbit 的作用：

• 节点 $x$ 管理的范围长度就是 $\text{lowbit}(x)$。
• 查询前缀和：$x = x - \text{lowbit}(x)$（向左上方跳）。
• 修改单点值：$x = x + \text{lowbit}(x)$（向右上方跳，更新受影响的父节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <vector>

class FenwickTree {
private:
    std::vector<int> tree;
    int n;

    // 核心：找到最低位的 1
    int lowbit(int x) {
        return x & -x;
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // 单点更新：将 index 位置的值加上 delta
    void update(int i, int delta) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += delta;
        }
    }

    // 查询前缀和：查询 [1, i] 的总和
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }

    // 区间查询：查询 [L, R] 的总和
    int queryRange(int L, int R) {
        if (L > R) return 0;
        return query(R) - query(L - 1);
    }
};

在树状数组中，节点 tree[i] 负责的区间长度是由 $i$ 的二进制表示中最低位的 1 及其后面的 0 决定的。

对于索引 $i$，它负责的范围是：

或者写成闭区间形式：

其中，$lowbit(i) = i \& (-i)$。

树状数组 vs 线段树

差分数组

差分数组是前缀和的逆运算。它最核心的用途是在 $O(1)$ 时间内完成区间修改。适用于所有的修改都完成后，才进行最终查询的情况

• 核心思想：维护相邻元素的差值 $D[i] = A[i] - A[i-1]$。
• 操作原理：
  • 区间修改：给区间 $[L, R]$ 加上 $v$，只需令 $D[L] += v$ 和 $D[R+1] -= v$。
  • 还原原数组：对 $D$ 求一遍前缀和，即可得到修改后的原数组。
• 优点：极简，修改极快（$O(1)$）。
• 缺点：不支持边改边查。每次查询某个值都需要 $O(n)$ 重新求前缀和。
• 适用场景：有大量的区间修改操作，且所有修改完成后才进行查询。

前缀和数组是用来快速计算“区间和”的，那么差分数组就是它的“孪生兄弟”，专门用来快速处理“区间修改”。

差分数组是前缀和的逆运算。它最核心的用途是在 $O(1)$ 时间内完成区间修改。

• 核心思想：维护相邻元素的差值 $D[i] = A[i] - A[i-1]$。
• 操作原理：
  • 区间修改：给区间 $[L, R]$ 加上 $v$，只需令 $D[L] += v$ 和 $D[R+1] -= v$。
  • 还原原数组：对 $D$ 求一遍前缀和，即可得到修改后的原数组。
• 优点：极简，修改极快（$O(1)$）。
• 缺点：不支持边改边查。每次查询某个值都需要 $O(n)$ 重新求前缀和。
• 适用场景：有大量的区间修改操作，且所有修改完成后才进行查询。

简单来说，差分数组能把 $O(n)$ 的区间增加操作，变成 $O(1)$ 的单点操作。

1. 核心定义

假设有一个原数组 $A$：$A = [a_1, a_2, a_3, \dots, a_n]$。

我们构造一个差分数组 $D$，满足：

• $D[1] = A[1]$
• $D[i] = A[i] - A[i-1]$ （对于 $i > 1$）

它的神奇特性是：

原数组 $A$ 的第 $i$ 项，等于差分数组 $D$ 前 $i$ 项的前缀和。

1. 为什么要用它？

想象一个场景：你需要给数组 $A$ 的区间 $[L, R]$ 里的每一个数都加上 $v$。

• 常规做法：写个 for 循环从 $L$ 扫到 $R$，复杂度 $O(n)$。
• 差分做法：只需修改 $D$ 数组的两个点：
  1. $D[L] += v$：这会让从 $L$ 开始往后的所有 $A[i]$ 在求前缀和时都加上了 $v$。
  2. $D[R+1] -= v$：这会让从 $R+1$ 开始往后的所有 $A[i]$ 把刚才多加的 $v$ 给减回去。

结论：一次区间修改只需两次赋值，复杂度 $O(1)$。

假设数组 $A = [3, 5, 2, 4, 1]$。

第一步：构建差分数组 $D$

• $D[1] = 3$

• $D[2] = 5 - 3 = 2$

• $D[3] = 2 - 5 = -3$

• $D[4] = 4 - 2 = 2$

• $D[5] = 1 - 4 = -3$

  此时 $D = [3, 2, -3, 2, -3]$。

第二步：执行区间修改

我们要给区间 $[2, 4]$（也就是元素 $5, 2, 4$）每个数都加上 10。

• $D[2] = 2 + 10 = 12$

• $D[4+1] = D[5] = -3 - 10 = -13$

  修改后的 $D = [3, 12, -3, 2, -13]$。

第三步：还原原数组 $A$

对 $D$ 求前缀和：

• $A’[1] = 3$
• $A’[2] = 3 + 12 = 15$ （原值 5 + 10，正确！）
• $A’[3] = 15 + (-3) = 12$ （原值 2 + 10，正确！）
• $A’[4] = 12 + 2 = 14$ （原值 4 + 10，正确！）
• $A’[5] = 14 + (-13) = 1$

经典题目

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> delta(101);
        const int offset = 1950;
        for (auto& p : logs) {
            delta[p[0] - offset]++;
            delta[p[1] - offset]--;
        }
        int max{}, res{}, cur{};
        for (int i = 0; i < delta.size(); i++) {
            cur += delta[i];
            if (cur > max) {
                max = cur;
                res = i;
            }
        }
        return res + offset;
    }
};

字母移位

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

如果需要永远返回正数的取模结果（例如在处理循环数组下标时），可以使用这个通用的“数学模”技巧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int sz = s.size();
        vector<int> delta(sz + 1);
        for (auto& shift : shifts) {
            if (shift[2] == 1) {
                delta[shift[0]] += shift[2];
                delta[shift[1] + 1] -= shift[2];
            } else {
                delta[shift[0]] -= 1;
                delta[shift[1] + 1] += 1;
            }
        }
        vector<int> nums(sz);
        int acc{};
        for (int i = 0; i < sz; i++) {
            acc += delta[i];
            nums[i] = acc;
        }
        for (int i = 0; i < sz; i++) {
            int n = (nums[i] % 26 + 26) % 26;
            s[i] = 'a' + (s[i] - 'a' + n) % 26;
        }
        return s;
    }
};

零数组变换I

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

• 在 nums 的下标范围 [li, ri] 内选择一个下标 子集。
• 将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int sz = nums.size();
        vector<int> delta(sz + 1);
        delta[0] = nums[0];
        for (int i = 1; i < sz; i++) {
            delta[i] = nums[i] - nums[i - 1];
        }
        for (auto& q : queries) {
            delta[q[0]] -= 1;
            delta[q[1] + 1] += 1;
        }
        int acc{};
        for (int i = 0; i < sz; i++) {
            acc += delta[i];
            if (acc > 0) {
                return false;
            }
        }
        return true;
    }
};

零数组变换 II

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示在 nums 上执行以下操作：

• 将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。
• 每个下标的减少的数值可以独立选择。

零数组 是指所有元素都等于 0 的数组。

返回 k 可以取到的 最小**非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组**。如果不存在这样的 k，则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    bool isValid(vector<int>& nums, vector<vector<int>>& queries, int k) {
        int sz = nums.size();
        vector<int> delta(sz + 1);
        // 初始化
        delta[0] = nums[0];
        for (int i = 1; i < sz; i++) {
            delta[i] = nums[i] - nums[i - 1];
        }
        for (int i = 0; i < k; i++) {
            auto& q = queries[i];
            delta[q[0]] -= q[2];
            delta[q[1] + 1] += q[2];
        }
        int acc{};
        for (int i = 0; i < sz; i++) {
            acc += delta[i];
            if (acc > 0) {
                return false;
            }
        }
        return true;
    }
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        // 先检查
        if(isValid(nums,queries,0)) {
            return 0;
        }
        int l = 1, r = queries.size();
        int ans{-1};
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (isValid(nums, queries, m)) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }
};

航班预定统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // 多个修改 一次查询
        vector<int> nums(n);
        // delta[i]表示bookings[i] - bookings[i-1]
        vector<int> delta(n + 1);
        for (auto& p : bookings) {
            delta[p[0] - 1] += p[2];
            delta[p[1]] -= p[2];
        }
        int acc{};
        for (int i = 0; i < n; i++) {
            acc += delta[i];
            nums[i] = acc;
        }
        return nums;
    }
};

使数组互补的最少操作次数

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        vector<int> arr(2 * limit + 2);
        int sz = nums.size();
        // 2-2*limit
        for (int i = 0; i < sz / 2; i++) {
            int a = nums[i];
            int b = nums[sz - 1 - i];
            int max_num = max(a, b);
            int min_num = min(a, b);
            arr[2] += 2;
            arr[2 * limit + 1] -= 2;

            arr[min_num + 1] -= 1;
            arr[max_num + limit + 1] += 1;

            arr[a + b] -= 1;
            arr[a + b + 1] += 1;
        }
        int acc{};
        int res{sz};
        // arr[i]表示和为i的操作次数arr[i]
        for (int i = 2; i < 2 * limit + 1; i++) {
            acc += arr[i];
            res = min(acc, res);
        }
        return res;
    }
};

二维区域和检索-区域不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

• 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class NumMatrix {
public:
    vector<vector<int>> prefixSum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefixSum.resize(1 + m);
        for (int i = 0; i <= m; i++) {
            prefixSum[i].resize(1 + n);
        }
        // 前缀和
        // prefix[i][j]表示左上角mat[0][0]到右下角mat[i-1][j-1]的和
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] -
                                  prefixSum[i - 1][j - 1] +
                                  matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] -
               prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

二维区域和检索-矩阵可修改

给你一个二维矩阵 matrix ，处理以下类型的多个查询:

1. 更新 matrix 中单元格的值。
2. 计算由 左上角 (row1, col1) 和 右下角 (row2, col2) 定义的 matrix 内矩阵元素的 和。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象。
• void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val 。
• int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵 matrix 中指定矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。

由于涉及到频繁的更新（update）和频繁的查询（sumRegion），我们不能使用静态的二维前缀和（因为更新一次需要 $O(n^2)$），也不能使用暴力遍历（因为查询一次需要 $O(n^2)$）。

最理想的方案是使用 二维树状数组（2D Binary Indexed Tree / Fenwick Tree）。它可以让更新和查询的时间复杂度都达到极佳的 $O(\log n \times \log m)$

树状数组（BIT）本质上是一种通过二进制分解来管理区间和的数据结构。在二维空间中，它相当于在行和列两个维度上各套了一层 BIT。

• update(row, col, delta)：当某个点的值改变时，我们需要沿着 BIT 的路径向上更新所有受影响的“块”。
• query(row, col)：查询从 $(0, 0)$ 到 $(row, col)$ 的前缀和。我们需要沿着路径向下累加。

二维容斥原理查询

当你有了 query(row, col) 函数后，计算任意矩形区域 $[row1, col1]$ 到 $[row2, col2]$ 的和，使用的正是你之前问过的那个容斥原理公式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class NumMatrix {
public:
    // 线段树范围更新
    // 线状数组单点更新，但可以多次进行批量更新
    vector<vector<int>> tree;
    vector<vector<int>> nums;
    int m;
    int n;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        this->nums.resize(m);
        for (int i = 0; i < m; i++) {
            this->nums[i].resize(n);
        }
        this->m = m;
        this->n = n;
        tree.resize(m + 1);
        for (int i = 0; i < tree.size(); i++) {
            tree[i].resize(n + 1);
        }
        // 更新
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                update(i - 1, j - 1, matrix[i - 1][j - 1]);
            }
        }
    }
    int lowbit(int x) { return x & -x; }
    void update(int row, int col, int val) {
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for (int i = row + 1; i <= m; i += lowbit(i)) {
            for (int j = col + 1; j <= n; j += lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }
    int query(int row, int col) {
        int res{};
        for (int i = row; i >= 1; i -= lowbit(i)) {
            for (int j = col; j >= 1; j -= lowbit(j)) {
                res += tree[i][j];
            }
        }
        return res;
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        // 前缀差
        // region = row2,col2 - row1,col2 - row2 col1 + row1,col1
        return query(row2 + 1, col2 + 1) - query(row1, col2 + 1) -
               query(row2 + 1, col1) + query(row1, col1);
    }
};