分享丨【算法题单】常用数据结构（前缀和/栈/队列/堆/字典树/并查集/树状数组/线段树）

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x
        self.s = s

    # 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        s = self.s
        return s[r2 + 1][c2 + 1] - s[r2 + 1][c1] - s[r1][c2 + 1] + s[r1][c1]

java

class NumMatrix {
    private final int[][] sum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        sum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
    }

    // 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
    }
}

cpp

class NumMatrix {
    vector<vector<int>> sum;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        sum.resize(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
    }

    // 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
    int sumRegion(int r1, int c1, int r2, int c2) {
        return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
    }
};

type NumMatrix [][]int

func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    sum := make([][]int, m+1)
    sum[0] = make([]int, n+1)
    for i, row := range matrix {
        sum[i+1] = make([]int, n+1)
        for j, x := range row {
            sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + x
        }
    }
    return sum
}

// 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
func (s NumMatrix) SumRegion(r1, c1, r2, c2 int) int {
    return s[r2+1][c2+1] - s[r2+1][c1] - s[r1][c2+1] + s[r1][c1]
}

304. 二维区域和检索 - 矩阵不可变
1314. 矩阵区域和 1484
3070. 元素和小于等于 k 的子矩阵的数目 1499
1738. 找出第 K 大的异或坐标值 1671
3212. 统计 X 和 Y 频数相等的子矩阵数量 1673
1292. 元素和小于等于阈值的正方形的最大边长 1735 可以优化到 $O (m n)$

二维前缀最小值：

3148. 矩阵中的最大得分 1820

二、差分

§2.1 一维差分

差分与前缀和的关系，类似导数与积分的关系。

数组 $a$ 的差分的前缀和就是数组 $a$ （不变）。

原理讲解

§2.1.1 基础

§2.1.2 进阶

思维扩展：

§2.2 二维差分

【图解】从一维差分到二维差分

三、栈

§3.1 基础

§3.2 进阶

§3.3 邻项消除

§3.4 合法括号字符串（RBS）

注：部分题目可以不用栈，而是用一个数字记录嵌套深度。

§3.5 表达式解析

§3.6 对顶栈

2296. 设计一个文本编辑器 1912 也可以用 Splay 树

§3.7 单调栈

见单调栈题单。

四、队列

队列常用在 BFS 中，见网格图题单和图论题单。与此相比，栈常用在 DFS 中，但无需我们手动维护。

§4.1 基础

§4.2 设计

§4.3 双端队列

2810. 故障键盘做到 $O (n)$
2071. 你可以安排的最多任务数目 2648

§4.4 单调队列

个人觉得叫单调双端队列更准确。

单调队列 = 滑动窗口 + 单调栈。必须先掌握滑动窗口和单调栈这两个知识点，再学单调队列。

问：入队、出队、更新答案，这三步的顺序如何思考？

答：有两种情况。如果更新答案时，用到的数据包含当前元素，那么就需要先入队，再更新答案；如果用到的数据不包含当前元素，那么就需要先更新答案，再入队。至于出队，一般写在前面，每遍历到一个新的元素，就看看队首元素是否失效（不满足要求），失效则弹出队首。

原理讲解

模板：

# 计算 nums 的每个长为 k 的窗口的最大值
# 时间复杂度 O(n)，其中 n 是 nums 的长度
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    ans = [0] * (len(nums) - k + 1)  # 窗口个数
    q = deque()  # 双端队列

    for i, x in enumerate(nums):
        # 1. 右边入
        while q and nums[q[-1]] <= x:
            q.pop()  # 维护 q 的单调性
        q.append(i)  # 注意保存的是下标，这样下面可以判断队首是否离开窗口

        # 2. 左边出
        left = i - k + 1  # 窗口左端点
        if q[0] < left:  # 队首离开窗口
            q.popleft()

        # 3. 在窗口左端点处记录答案
        if left >= 0:
            # 由于队首到队尾单调递减，所以窗口最大值就在队首
            ans[left] = nums[q[0]]

    return ans

java

class Solution {
    // 计算 nums 的每个长为 k 的窗口的最大值
    // 时间复杂度 O(n)，其中 n 是 nums 的长度
    private int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1]; // 窗口个数
        Deque<Integer> q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. 右边入
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast(); // 维护 q 的单调性
            }
            q.addLast(i); // 注意保存的是下标，这样下面可以判断队首是否离开窗口

            // 2. 左边出
            int left = i - k + 1; // 窗口左端点
            if (q.getFirst() < left) { // 队首离开窗口
                q.removeFirst();
            }

            // 3. 在窗口左端点处记录答案
            if (left >= 0) {
                // 由于队首到队尾单调递减，所以窗口最大值就在队首
                ans[left] = nums[q.getFirst()];
            }
        }

        return ans;
    }
}

cpp

// 计算 nums 的每个长为 k 的窗口的最大值
// 时间复杂度 O(n)，其中 n 是 nums 的长度
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> ans(n - k + 1); // 窗口个数
    deque<int> q; // 双端队列

    for (int i = 0; i < n; i++) {
        // 1. 右边入
        while (!q.empty() && nums[q.back()] <= nums[i]) {
            q.pop_back(); // 维护 q 的单调性
        }
        q.push_back(i); // 注意保存的是下标，这样下面可以判断队首是否离开窗口

        // 2. 左边出
        int left = i - k + 1; // 窗口左端点
        if (q.front() < left) { // 队首离开窗口
            q.pop_front();
        }

        // 3. 在窗口左端点处记录答案
        if (left >= 0) {
            // 由于队首到队尾单调递减，所以窗口最大值就在队首
            ans[left] = nums[q.front()];
        }
    }

    return ans;
}

// 计算 nums 的每个长为 k 的窗口的最大值
// 时间复杂度 O(n)，其中 n 是 nums 的长度
func maxSlidingWindow(nums []int, k int) []int {
    ans := make([]int, len(nums)-k+1) // 窗口个数
    q := []int{}

    for i, x := range nums {
        // 1. 右边入
        for len(q) > 0 && nums[q[len(q)-1]] <= x {
            q = q[:len(q)-1] // 维护 q 的单调性
        }
        q = append(q, i) // 注意保存的是下标，这样下面可以判断队首是否离开窗口

        // 2. 左边出
        left := i - k + 1 // 窗口左端点
        if q[0] < left {  // 队首离开窗口
            q = q[1:] // Go 的切片是 O(1) 的
        }

        // 3. 在窗口左端点处记录答案
        if left >= 0 {
            // 由于队首到队尾单调递减，所以窗口最大值就在队首
            ans[left] = nums[q[0]]
        }
    }

    return ans
}

关于单调队列优化 DP，见动态规划题单的「§11.3 单调队列优化 DP」。

五、堆（优先队列）

§5.1 基础

为什么堆化的时间复杂度是 O(n)？

§5.2 进阶

有序集合：

§5.3 第 K 小/大

部分题目也可以用二分解决。

§5.4 重排元素

984. 不含 AAA 或 BBB 的字符串 1474 不需要堆，这题的目的是引入贪心思想
767. 重构字符串 1681
1054. 距离相等的条形码 1702
1405. 最长快乐字符串 1821
3081. 替换字符串中的问号使分数最小 1905
621. 任务调度器
358. K 距离间隔重排字符串（会员题）

§5.5 反悔堆

基于堆的反悔贪心。

LCP 30. 魔塔游戏
1642. 可以到达的最远建筑 1962
630. 课程表 III
871. 最低加油次数 2074
3362. 零数组变换 III 2424 虽然没有反悔的过程，但思路和 871 是类似的
2813. 子序列最大优雅度 2582 也可以不用堆
1388. 3n 块披萨做到 $O (n \log n)$
3892. 产生至少 K 个峰值的最少操作次数做到 $O (n \log n)$
3049. 标记所有下标的最早秒数 II 3111
3711. 不出现负余额的最大交易额（会员题）
2599. 使前缀和数组非负（会员题）

§5.6 懒删除堆

支持删除堆中任意元素。

模板：

# 模板来源 ./09-常用数据结构
class LazyHeap:
    def __init__(self):
        self.heap = []  # 最小堆（最大堆可以把数字取反或重载 __lt__）
        self.remove_cnt = defaultdict(int)  # 每个元素剩余需要删除的次数
        self.size = 0  # 堆的实际大小

    # 删除
    def remove(self, x: Any) -> None:
        self.remove_cnt[x] += 1  # 懒删除
        self.size -= 1

    # 正式执行删除操作
    def _apply_remove(self) -> None:
        while self.heap and self.remove_cnt[self.heap[0]] > 0:
            self.remove_cnt[self.heap[0]] -= 1
            heappop(self.heap)

    # 查看堆顶
    def top(self) -> Any:
        self._apply_remove()
        return self.heap[0]  # 真正的堆顶

    # 出堆
    def pop(self) -> Any:
        self._apply_remove()
        self.size -= 1
        return heappop(self.heap)

    # 入堆
    def push(self, x: Any) -> None:
        if self.remove_cnt[x] > 0:
            self.remove_cnt[x] -= 1  # 抵消之前的删除
        else:
            heappush(self.heap, x)
        self.size += 1

java

// 模板来源 ./09-常用数据结构
// 最小堆 LazyHeap minPQ = new LazyHeap(Integer::compare);
// 最大堆 LazyHeap maxPQ = new LazyHeap((a, b) -> Integer.compare(b, a));
class LazyHeap extends PriorityQueue<Integer> {
    private final Map<Integer, Integer> removeCnt = new HashMap<>(); // 每个元素剩余需要删除的次数
    private int size = 0; // 堆的实际大小

    public LazyHeap(Comparator<Integer> comparator) {
        super(comparator);
    }

    // 删除堆中所有应该删除的元素后，堆的实际大小
    public int size() {
        return size;
    }

    // 删除
    public void remove(int x) {
        removeCnt.merge(x, 1, Integer::sum); // 懒删除
        size--;
    }

    // 正式执行删除操作
    private void applyRemove() {
        while (removeCnt.getOrDefault(peek(), 0) > 0) {
            removeCnt.merge(poll(), -1, Integer::sum);
        }
    }

    // 查看堆顶
    public int top() {
        applyRemove();
        return peek(); // 真正的堆顶
    }

    // 出堆
    public int pop() {
        applyRemove();
        size--;
        return poll();
    }

    // 入堆
    public void push(int x) {
        int c = removeCnt.getOrDefault(x, 0);
        if (c > 0) {
            removeCnt.put(x, c - 1); // 抵消之前的删除
        } else {
            offer(x);
        }
        size++;
    }
}

cpp

// 模板来源 ./09-常用数据结构
// 最大堆 LazyHeap<int> max_pq;
// 最小堆 LazyHeap<int, greater<>> min_pq;
template<typename T, typename Compare = less<T>>
class LazyHeap {
    priority_queue<T, vector<T>, Compare> pq;
    unordered_map<T, int> remove_cnt; // 每个元素剩余需要删除的次数
    size_t sz = 0; // 堆的实际大小

    // 正式执行删除操作
    void apply_remove() {
        while (!pq.empty() && remove_cnt[pq.top()] > 0) {
            remove_cnt[pq.top()]--;
            pq.pop();
        }
    }

public:
    // 删除堆中所有应该删除的元素后，堆的实际大小
    size_t size() {
        return sz;
    }

    // 删除
    void remove(T x) {
        remove_cnt[x]++; // 懒删除
        sz--;
    }

    // 查看堆顶
    T top() {
        apply_remove();
        return pq.top(); // 真正的堆顶
    }

    // 出堆
    T pop() {
        apply_remove();
        sz--;
        T x = pq.top();
        pq.pop();
        return x;
    }

    // 入堆
    void push(T x) {
        if (remove_cnt[x] > 0) {
            remove_cnt[x]--; // 抵消之前的删除
        } else {
            pq.push(x);
        }
        sz++;
    }
};

// 模板来源 ./09-常用数据结构
func newLazyHeap() *lazyHeap {
	return &lazyHeap{removeCnt: map[int]int{}}
}

// 懒删除堆（默认是最小堆）
type lazyHeap struct {
	sort.IntSlice
	removeCnt map[int]int // 每个元素剩余需要删除的次数
	size      int         // 堆的实际大小
}

// 必须实现的两个接口
func (h *lazyHeap) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *lazyHeap) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

// 加上这行变成最大堆
// func (h *lazyHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

// 删除
func (h *lazyHeap) remove(v int) {
	h.removeCnt[v]++ // 懒删除
	h.size--
}

// 正式执行删除操作
func (h *lazyHeap) applyRemove() {
	for h.removeCnt[h.IntSlice[0]] > 0 {
		h.removeCnt[h.IntSlice[0]]--
		heap.Pop(h)
	}
}

// 查看堆顶
func (h *lazyHeap) top() int {
	h.applyRemove()
	return h.IntSlice[0] // 真正的堆顶
}

// 出堆
func (h *lazyHeap) pop() int {
	h.applyRemove()
	h.size--
	return heap.Pop(h).(int)
}

// 入堆
func (h *lazyHeap) push(v int) {
	if h.removeCnt[v] > 0 {
		h.removeCnt[v]-- // 抵消之前的删除
	} else {
		heap.Push(h, v)
	}
	h.size++
}

§5.7 对顶堆（动态第 K 小/大）

讲解

部分题目需要结合懒删除堆。

做法不止一种，部分题目也可以用有序集合/值域树状数组等数据结构解决，见本题单「§8.1 树状数组」的模板二。

2102. 序列顺序查询 2159
295. 数据流的中位数
480. 滑动窗口中位数
2653. 滑动子数组的美丽值非暴力做法
1825. 求出 MK 平均值 2396
3505. 使 K 个子数组内元素相等的最少操作数 2539 滑动窗口中位数的距离和
3013. 将数组分成最小总代价的子数组 II 2540
3321. 计算子数组的 x-sum II 2598
3962. 至多 K 次交换后最大子数组和 2672
LCP 24. 数字游戏
3369. 设计数组统计跟踪器（会员题）
3422. 将子数组元素变为相等所需的最小操作数（会员题）

另见图论题单中的 Dijkstra 算法。

六、字典树（trie）

§6.1 基础

讲解（含模板代码）

§6.2 进阶

思维扩展：

440. 字典序的第K小数字

§6.3 字典树优化 DP

§6.4 0-1 字典树（异或字典树）

部分题目也可以用试填法解决。

七、并查集

模板：

# 模板来源 ./09-常用数据结构
class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己，大小为 1
        self._fa = list(range(n))  # 代表元
        self._size = [1] * n  # 集合大小
        self.cc = n  # 连通块个数

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        fa = self._fa
        # 如果 fa[x] == x，则表示 x 是代表元
        if fa[x] != x:
            fa[x] = self.find(fa[x])  # fa 改成代表元
        return fa[x]

    # 判断 x 和 y 是否在同一个集合
    def is_same(self, x: int, y: int) -> bool:
        # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return self.find(x) == self.find(y)

    # 把 from 所在集合合并到 to 所在集合中
    # 返回是否合并成功
    def merge(self, from_: int, to: int) -> bool:
        x, y = self.find(from_), self.find(to)
        if x == y:  # from 和 to 在同一个集合，不做合并
            return False
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        self._size[y] += self._size[x]  # 更新集合大小（注意集合大小保存在代表元上）
        # 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x]
        self.cc -= 1  # 成功合并，连通块个数减一
        return True

    # 返回 x 所在集合的大小
    def get_size(self, x: int) -> int:
        return self._size[self.find(x)]  # 集合大小保存在代表元上

java

// 模板来源 ./09-常用数据结构
class UnionFind {
    private final int[] fa; // 代表元
    private final int[] size; // 集合大小
    public int cc; // 连通块个数

    UnionFind(int n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己，大小为 1
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
        size = new int[n];
        Arrays.fill(size, 1);
        cc = n;
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    public int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    public boolean isSame(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    // 返回是否合并成功
    public boolean merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return false;
        }
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        size[y] += size[x]; // 更新集合大小（注意集合大小保存在代表元上）
        // 无需更新 size[x]，因为我们不用 size[x] 而是用 size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 size[x]
        cc--; // 成功合并，连通块个数减一
        return true;
    }

    // 返回 x 所在集合的大小
    public int getSize(int x) {
        return size[find(x)]; // 集合大小保存在代表元上
    }
}

cpp

// 模板来源 ./09-常用数据结构
class UnionFind {
    vector<int> fa; // 代表元
    vector<int> sz; // 集合大小

public:
    int cc; // 连通块个数

    UnionFind(int n) : fa(n), sz(n, 1), cc(n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己，大小为 1
        ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合
    bool is_same(int x, int y) {
        // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return find(x) == find(y);
    }

    // 把 from 所在集合合并到 to 所在集合中
    // 返回是否合并成功
    bool merge(int from, int to) {
        int x = find(from), y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return false;
        }
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        sz[y] += sz[x]; // 更新集合大小（注意集合大小保存在代表元上）
        // 无需更新 sz[x]，因为我们不用 sz[x] 而是用 sz[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 sz[x]
        cc--; // 成功合并，连通块个数减一
        return true;
    }

    // 返回 x 所在集合的大小
    int get_size(int x) {
        return sz[find(x)]; // 集合大小保存在代表元上
    }
};

// 模板来源 ./09-常用数据结构
type unionFind struct {
    fa []int // 代表元
    sz []int // 集合大小
    cc int   // 连通块个数
}

func newUnionFind(n int) unionFind {
    fa := make([]int, n)
    sz := make([]int, n)
    // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
    // 集合 i 的代表元是自己，大小为 1
    for i := range fa {
        fa[i] = i
        sz[i] = 1
    }
    return unionFind{fa, sz, n}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
    // 如果 fa[x] == x，则表示 x 是代表元
    if u.fa[x] != x {
        u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
    }
    return u.fa[x]
}

// 判断 x 和 y 是否在同一个集合
func (u unionFind) same(x, y int) bool {
    // 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
    // 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
    return u.find(x) == u.find(y)
}

// 把 from 所在集合合并到 to 所在集合中
// 返回是否合并成功
func (u *unionFind) merge(from, to int) bool {
    x, y := u.find(from), u.find(to)
    if x == y { // from 和 to 在同一个集合，不做合并
        return false
    }
    u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
    u.sz[y] += u.sz[x] // 更新集合大小（注意集合大小保存在代表元上）
    // 无需更新 sz[x]，因为我们不用 sz[x] 而是用 sz[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 sz[x]
    u.cc-- // 成功合并，连通块个数减一
    return true
}

// 返回 x 所在集合的大小
func (u unionFind) size(x int) int { 
    return u.sz[u.find(x)] // 集合大小保存在代表元上
}

§7.1 基础

更多基础题，见网格图题单中的 DFS 和图论题单中的 DFS，其中大部分题目也可以用并查集实现。

§7.2 进阶

另见图论题单中的最小生成树。

§7.3 中介并查集

把 $n$ 个元素两两相连，要连 $O (n^{2})$ 条边，太慢了。而把元素连到中介上，通常只会连 $O (n)$ 条边。

§7.4 数组上的并查集

§7.5 区间并查集

§7.6 带权并查集（边权并查集）

模板：

# 模板来源 ./09-常用数据结构
class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己，自己到自己的距离是 0
        self.fa = list(range(n))  # 代表元
        self.dis = [0] * n  # dis[x] 表示 x 到（x 所在集合的）代表元的距离

    # 返回 x 所在集合的代表元
    # 同时做路径压缩
    def find(self, x: int) -> int:
        fa = self.fa
        if fa[x] != x:
            root = self.find(fa[x])
            self.dis[x] += self.dis[fa[x]]  # 递归更新 x 到其代表元的距离
            fa[x] = root
        return fa[x]

    # 判断 x 和 y 是否在同一个集合（同普通并查集）
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    # 计算从 from 到 to 的相对距离
    # 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
    def get_relative_distance(self, from_: int, to: int) -> int:
        self.find(from_)
        self.find(to)
        # to-from = (x-from) - (x-to) = dis[from] - dis[to]
        return self.dis[from_] - self.dis[to]

    # 合并 from 和 to，新增信息 to - from = value
    # 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
    # 如果 from 和 to 不在同一个集合，返回 True，否则返回是否与已知信息矛盾
    def merge(self, from_: int, to: int, value: int) -> bool:
        x, y = self.find(from_), self.find(to)
        dis = self.dis
        if x == y:  # from 和 to 在同一个集合，不做合并
            # to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
            return dis[from_] - dis[to] == value
        #    x --------- y
        #   /           /
        # from ------- to
        # 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
        # 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
        # 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
        dis[x] = value + dis[to] - dis[from_]  # 计算 x 到其代表元 y 的距离
        self.fa[x] = y
        return True

java

// 模板来源 ./09-常用数据结构
class UnionFind {
    private final int[] fa; // 代表元
    private final int[] dis; // dis[x] 表示 x 到（x 所在集合的）代表元的距离
    // 注意数据范围，必要时使用 long[] dis

    public UnionFind(int n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己，自己到自己的距离是 0
        fa = new int[n];
        dis = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩
    public int find(int x) {
        if (fa[x] != x) {
            int root = find(fa[x]);
            dis[x] += dis[fa[x]]; // 递归更新 x 到其代表元的距离
            fa[x] = root;
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合（同普通并查集）
    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    // 计算从 from 到 to 的相对距离
    // 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
    public int getRelativeDistance(int from, int to) {
        find(from);
        find(to);
        // to-from = (x-from) - (x-to) = dis[from] - dis[to]
        return dis[from] - dis[to];
    }

    // 合并 from 和 to，新增信息 to - from = value
    // 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
    // 如果 from 和 to 不在同一个集合，返回 true，否则返回是否与已知信息矛盾
    public boolean merge(int from, int to, int value) {
        int x = find(from), y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            // to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
            return dis[from] - dis[to] == value;
        }
        //    x --------- y
        //   /           /
        // from ------- to
        // 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
        // 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
        // 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
        dis[x] = value + dis[to] - dis[from]; // 计算 x 到其代表元 y 的距离
        fa[x] = y;
        return true;
    }
}

cpp

// 模板来源 ./09-常用数据结构
// 根据题目用 UnionFind<int> uf(n) 或者 UnionFind<long long> uf(n) 初始化
template<typename T>
class UnionFind {
public:
    vector<int> fa; // 代表元
    vector<T> dis; // dis[x] 表示 x 到（x 所在集合的）代表元的距离

    UnionFind(int n) : fa(n), dis(n) {
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己，自己到自己的距离是 0
        ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩
    int find(int x) {
        if (fa[x] != x) {
            int root = find(fa[x]);
            dis[x] += dis[fa[x]]; // 递归更新 x 到其代表元的距离
            fa[x] = root;
        }
        return fa[x];
    }

    // 判断 x 和 y 是否在同一个集合（同普通并查集）
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 计算从 from 到 to 的相对距离
    // 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
    T get_relative_distance(int from, int to) {
        find(from);
        find(to);
        // to-from = (x-from) - (x-to) = dis[from] - dis[to]
        return dis[from] - dis[to];
    }

    // 合并 from 和 to，新增信息 to - from = value
    // 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
    // 如果 from 和 to 不在同一个集合，返回 true，否则返回是否与已知信息矛盾
    bool merge(int from, int to, T value) {
        int x = find(from), y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            // to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
            return dis[from] - dis[to] == value;
        }
        //    x --------- y
        //   /           /
        // from ------- to
        // 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
        // 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
        // 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
        dis[x] = value + dis[to] - dis[from]; // 计算 x 到其代表元 y 的距离
        fa[x] = y;
        return true;
    }
};

// 模板来源 ./09-常用数据结构
type unionFind struct {
    fa  []int // 代表元
    dis []int // dis[x] 表示 x 到（x 所在集合的）代表元的距离
}

func newUnionFind(n int) unionFind {
    // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
    // 集合 i 的代表元是自己，自己到自己的距离是 0
    fa := make([]int, n)
    dis := make([]int, n)
    for i := range fa {
        fa[i] = i
    }
    return unionFind{fa, dis}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩
func (u unionFind) find(x int) int {
    if u.fa[x] != x {
        root := u.find(u.fa[x])
        u.dis[x] += u.dis[u.fa[x]] // 递归更新 x 到其代表元的距离
        u.fa[x] = root
    }
    return u.fa[x]
}

// 判断 x 和 y 是否在同一个集合（同普通并查集）
func (u unionFind) same(x, y int) bool {
    return u.find(x) == u.find(y)
}

// 计算从 from 到 to 的相对距离
// 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
func (u unionFind) getRelativeDistance(from, to int) int {
    u.find(from)
    u.find(to)
    // to-from = (x-from) - (x-to) = dis[from] - dis[to]
    return u.dis[from] - u.dis[to]
}

// 合并 from 和 to，新增信息 to - from = value
// 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
// 如果 from 和 to 不在同一个集合，返回 true，否则返回是否与已知信息矛盾
func (u unionFind) merge(from, to int, value int) bool {
    x, y := u.find(from), u.find(to)
    if x == y { // from 和 to 在同一个集合，不做合并
        // to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
        return u.dis[from]-u.dis[to] == value
    }
    //    x --------- y
    //   /           /
    // from ------- to
    // 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
    // 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
    // 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
    u.dis[x] = value + u.dis[to] - u.dis[from] // 计算 x 到其代表元 y 的距离
    u.fa[x] = y
    return true
}

附加模板题：CF1850H

八、树状数组和线段树

能用树状数组解决的题目，也能用线段树解决（反过来不一定）。但树状数组实现简单，代码短。

为方便大家练习，我把适合用树状数组解决的题目分到树状数组中，其余分到线段树中。

部分题目需要用到离散化，推荐先完成 1331. 数组序号转换。

§8.1 树状数组

讲解：带你发明树状数组！附数学证明

模板一：普通树状数组

# 模板来源 ./09-常用数据结构
class FenwickTree:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)  # 使用下标 1 到 n

    # a[i] 增加 val
    # 1 <= i <= n
    # 时间复杂度 O(log n)
    def update(self, i: int, val: int) -> None:
        t = self.tree
        while i < len(t):
            t[i] += val
            i += i & -i

    # 计算前缀和 a[1] + ... + a[i]
    # 1 <= i <= n
    # 时间复杂度 O(log n)
    def pre(self, i: int) -> int:
        t = self.tree
        res = 0
        while i > 0:
            res += t[i]
            i &= i - 1
        return res

    # 计算区间和 a[l] + ... + a[r]
    # 1 <= l <= r <= n
    # 时间复杂度 O(log n)
    def query(self, l: int, r: int) -> int:
        if r < l:
            return 0
        return self.pre(r) - self.pre(l - 1)

java

// 模板来源 ./09-常用数据结构
class FenwickTree {
    private final long[] tree; // 如果计算结果没有超出 int 范围，可以改成 int

    public FenwickTree(int n) {
        tree = new long[n + 1]; // 使用下标 1 到 n
    }

    // a[i] 增加 val
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    public void update(int i, long val) {
        for (; i < tree.length; i += i & -i) {
            tree[i] += val;
        }
    }

    // 求前缀和 a[1] + ... + a[i]
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    public long pre(int i) {
        long res = 0;
        for (; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 求区间和 a[l] + ... + a[r]
    // 1 <= l <= r <= n
    // 时间复杂度 O(log n)
    public long query(int l, int r) {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);
    }
}

cpp

// 模板来源 ./09-常用数据结构
// 根据题目用 FenwickTree<int> t(n) 或者 FenwickTree<long long> t(n) 初始化
template<typename T>
class FenwickTree {
    vector<T> tree;

public:
    // 使用下标 1 到 n
    FenwickTree(int n) : tree(n + 1) {}

    // a[i] 增加 val
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    void update(int i, T val) {
        for (; i < tree.size(); i += i & -i) {
            tree[i] += val;
        }
    }

    // 求前缀和 a[1] + ... + a[i]
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    T pre(int i) const {
        T res{};
        for (; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 求区间和 a[l] + ... + a[r]
    // 1 <= l <= r <= n
    // 时间复杂度 O(log n)
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);
    }
};

// 模板来源 ./09-常用数据结构
type fenwick []int

func newFenwickTree(n int) fenwick {
    return make(fenwick, n+1) // 使用下标 1 到 n
}

// a[i] 增加 val
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) update(i int, val int) {
    for ; i < len(f); i += i & -i {
        f[i] += val
    }
}

// 求前缀和 a[1] + ... + a[i]
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) pre(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res += f[i]
    }
    return
}

// 求区间和 a[l] + ... + a[r]
// 1 <= l <= r <= n
// 时间复杂度 O(log n)
func (f fenwick) query(l, r int) int {
    if r < l {
        return 0
    }
    return f.pre(r) - f.pre(l-1)
}

模板二：值域树状数组

# 应用：https://leetcode.cn/problems/maximum-subarray-sum-after-at-most-k-swaps/
class FenwickTree:
    def __init__(self, sorted_nums: List[int]):
        self.n = n = len(sorted_nums)
        self.high_bit = 1 << (n.bit_length() - 1)
        self.sorted_nums = sorted_nums
        self.cnt = [0] * (n + 1)
        self.sum = [0] * (n + 1)

    # 添加 num 个 val，其中 val 离散化后的值为 i（i 从 1 开始）
    # 如果 num < 0，表示减少 -num 个 val
    # 注意 val = sorted_nums[i - 1]，无需手动传入
    def update(self, i: int, num: int) -> None:
        val = self.sorted_nums[i - 1]
        while i <= self.n:
            self.cnt[i] += num
            self.sum[i] += num * val
            i += i & -i

    # 返回第 k 小的数（k 从 1 开始）
    def kth(self, k: int) -> int:
        i = 0
        b = self.high_bit
        while b > 0:
            nxt = i | b
            if nxt <= self.n and self.cnt[nxt] < k:
                k -= self.cnt[nxt]
                i = nxt
            b >>= 1
        return self.sorted_nums[i]

    # 返回前 k 小的数之和（k 从 1 开始）
    def pre_sum(self, k: int) -> int:
        s = i = 0
        b = self.high_bit
        while b > 0:
            nxt = i | b
            if nxt <= self.n and self.cnt[nxt] < k:
                k -= self.cnt[nxt]
                s += self.sum[nxt]
                i = nxt
            b >>= 1
        # 加上等于第 k 小的数
        return s + self.sorted_nums[i] * k

java

// 应用：https://leetcode.cn/problems/maximum-subarray-sum-after-at-most-k-swaps/
class FenwickTree {
    private final int highBit;
    private final int[] sorted;
    private final int[] cnt;
    private final long[] sum;

    public FenwickTree(int[] sorted) {
        int n = sorted.length;
        highBit = Integer.highestOneBit(n);
        this.sorted = sorted;
        cnt = new int[n + 1];
        sum = new long[n + 1];
    }

    // 添加 num 个 val，其中 val 离散化后的值为 i（i 从 1 开始）
    // 如果 num < 0，表示减少 -num 个 val
    // 注意 val = sorted[i - 1]，无需手动传入
    public void update(int i, int num) {
        int val = sorted[i - 1];
        for (; i < cnt.length; i += i & -i) {
            cnt[i] += num;
            sum[i] += (long) num * val;
        }
    }

    // 返回第 k 小的数（k 从 1 开始）
    public int kth(int k) {
        int i = 0;
        for (int b = highBit; b > 0; b >>= 1) {
            int nxt = i | b;
            if (nxt < cnt.length && cnt[nxt] < k) {
                k -= cnt[nxt];
                i = nxt;
            }
        }
        return sorted[i];
    }

    // 返回前 k 小的数之和（k 从 1 开始）
    public long preSum(int k) {
        long s = 0;
        int i = 0;
        for (int b = highBit; b > 0; b >>= 1) {
            int nxt = i | b;
            if (nxt < cnt.length && cnt[nxt] < k) {
                k -= cnt[nxt];
                s += sum[nxt];
                i = nxt;
            }
        }
        // 加上等于第 k 小的数
        return s + (long) sorted[i] * k;
    }
}

cpp

// 应用：https://leetcode.cn/problems/maximum-subarray-sum-after-at-most-k-swaps/
class FenwickTree {
    const vector<int>& sorted;
    const int high_bit;
    vector<int> cnt;
    vector<long long> sum;

public:
    FenwickTree(const vector<int>& sorted) :
        sorted(sorted),
        high_bit(1 << (bit_width(sorted.size()) - 1)),
        cnt(sorted.size() + 1),
        sum(sorted.size() + 1) {}

    // 添加 num 个 val，其中 val 离散化后的值为 i（i 从 1 开始）
    // 如果 num < 0，表示减少 -num 个 val
    // 注意 val = sorted[i - 1]，无需手动传入
    void update(int i, int num) {
        auto val = sorted[i - 1];
        for (; i < cnt.size(); i += i & -i) {
            cnt[i] += num;
            sum[i] += 1LL * num * val;
        }
    }

    // 返回第 k 小的数（k 从 1 开始）
    int kth(int k) const {
        int i = 0;
        for (int b = high_bit; b > 0; b >>= 1) {
            int nxt = i | b;
            if (nxt < cnt.size() && cnt[nxt] < k) {
                k -= cnt[nxt];
                i = nxt;
            }
        }
        return sorted[i];
    }

    // 返回前 k 小的数之和（k 从 1 开始）
    long long pre_sum(int k) const {
        long long s = 0;
        int i = 0;
        for (int b = high_bit; b > 0; b >>= 1) {
            int nxt = i | b;
            if (nxt < cnt.size() && cnt[nxt] < k) {
                k -= cnt[nxt];
                s += sum[nxt];
                i = nxt;
            }
        }
        // 加上等于第 k 小的数
        return s + 1LL * sorted[i] * k;
    }
};

// 应用：https://leetcode.cn/problems/maximum-subarray-sum-after-at-most-k-swaps/
type pair struct{ cnt, sum int }
type fenwick struct {
	t       []pair
	sorted  []int
	highBit int
}

func newFenwickTree(sorted []int) fenwick {
	n := len(sorted)
	return fenwick{
		t:       make([]pair, n+1),
		sorted:  sorted,
		highBit: 1 << (bits.Len(uint(n)) - 1),
	}
}

// 添加 num 个 val，其中 val 离散化后的值为 i（i 从 1 开始）
// 如果 num < 0，表示减少 -num 个 val
// 注意 val = sorted[i-1]，无需手动传入
func (f *fenwick) update(i, num int) {
	val := f.sorted[i-1]
	for ; i < len(f.t); i += i & -i {
		f.t[i].cnt += num
		f.t[i].sum += num * val
	}
}

// 返回第 k 小的数（k 从 1 开始）
func (f *fenwick) kth(k int) int {
	i := 0
	for b := f.highBit; b > 0; b >>= 1 {
		if nxt := i | b; nxt < len(f.t) && f.t[nxt].cnt < k {
			k -= f.t[nxt].cnt
			i = nxt
		}
	}
	return f.sorted[i]
}

// 返回前 k 小的数之和（k 从 1 开始）
func (f *fenwick) preSum(k int) (s int) {
	i := 0
	for b := f.highBit; b > 0; b >>= 1 {
		if nxt := i | b; nxt < len(f.t) && f.t[nxt].cnt < k {
			k -= f.t[nxt].cnt
			s += f.t[nxt].sum
			i = nxt
		}
	}
	// 加上等于第 k 小的数
	s += f.sorted[i] * k
	return
}

另见本题单的「§5.7 对顶堆」，部分题目也可以用权值树状数组第 $k$ 小解决。

§8.2 逆序对

除了可以用树状数组解决，部分题目也可以在归并排序的同时计算。

§8.3 线段树（无区间更新）

线段树本质是二叉树，在学习之前，建议先做做 104. 二叉树的最大深度和 111. 二叉树的最小深度（自底向上写法），当作热身。

线段树：为什么要这样设计？理解线段树发明的动机。

把任意区间用 $O (\log n)$ 个区间表示，线段树的每个节点记录对应区间的信息。

询问：把询问区间拆分成 $O (\log n)$ 个区间，对应着线段树的 $O (\log n)$ 个节点，把这 $O (\log n)$ 个节点的信息合并，即为答案。
单点更新：有 $O (\log n)$ 个区间包含被修改的位置，需要更新 $O (\log n)$ 个节点的信息。

基础模板代码如下。为方便入门理解，我没有做复杂封装。更通用的写法可以参考 AtCoder Library 的 segtree.hpp。

# 模板来源 ./09-常用数据结构
# 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
# 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
# 区间的下标：从 0 开始
class SegmentTree:
    def __init__(self, arr, default=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
        # arr 可以是 list 或者 int
        # 如果 arr 是 int，视作数组大小，默认值为 default
        if isinstance(arr, int):
            arr = [default] * arr
        n = len(arr)
        self._n = n
        self._tree = [0] * (2 << (n - 1).bit_length())
        self._build(arr, 1, 0, n - 1)

    # 合并两个 val
    def _merge_val(self, a: int, b: int) -> int:
        return max(a, b)  # **根据题目修改**

    # 合并左右儿子的 val 到当前节点的 val
    def _maintain(self, node: int) -> None:
        self._tree[node] = self._merge_val(self._tree[node * 2], self._tree[node * 2 + 1])

    # 用 a 初始化线段树
    # 时间复杂度 O(n)
    def _build(self, a: List[int], node: int, l: int, r: int) -> None:
        if l == r:  # 叶子
            self._tree[node] = a[l]  # 初始化叶节点的值
            return
        m = (l + r) // 2
        self._build(a, node * 2, l, m)  # 初始化左子树
        self._build(a, node * 2 + 1, m + 1, r)  # 初始化右子树
        self._maintain(node)

    def _update(self, node: int, l: int, r: int, i: int, val: int) -> None:
        if l == r:  # 叶子（到达目标）
            # 如果想直接替换的话，可以写 self._tree[node] = val
            self._tree[node] = self._merge_val(self._tree[node], val)
            return
        m = (l + r) // 2
        if i <= m:  # i 在左子树
            self._update(node * 2, l, m, i, val)
        else:  # i 在右子树
            self._update(node * 2 + 1, m + 1, r, i, val)
        self._maintain(node)

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内
            return self._tree[node]
        m = (l + r) // 2
        if qr <= m:  # [ql, qr] 与右子树无交集，仅需递归左子树
            return self._query(node * 2, l, m, ql, qr)
        if ql > m:  # [ql, qr] 与左子树无交集，仅需递归右子树
            return self._query(node * 2 + 1, m + 1, r, ql, qr)
        # [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        l_res = self._query(node * 2, l, m, ql, qr)
        r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
        return self._merge_val(l_res, r_res)

    # 更新 a[i] 为 _merge_val(a[i], val)
    # 时间复杂度 O(log n)
    def update(self, i: int, val: int) -> None:
        self._update(1, 0, self._n - 1, i, val)

    # 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    # 时间复杂度 O(log n)
    def query(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self._n - 1, ql, qr)

    # 获取 a[i] 的值
    # 时间复杂度 O(log n)
    def get(self, i: int) -> int:
        return self._query(1, 0, self._n - 1, i, i)

java

// 模板来源 ./09-常用数据结构
// 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
// 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
// 区间的下标：从 0 开始
class SegmentTree {
    private final int n;
    private final long[] tree; // 如果计算结果没有超出 int 范围，可以改成 int

    // 合并两个 val
    private long mergeVal(long a, long b) {
        return Math.max(a, b); // **根据题目修改**
    }

    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 initVal
    public SegmentTree(int n, long initVal) {
        this.n = n;
        long[] a = new long[n];
        Arrays.fill(a, initVal);
        tree = new long[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        build(a, 1, 0, n - 1);
    }

    // 线段树维护数组 a
    public SegmentTree(long[] a) {
        n = a.length;
        tree = new long[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        build(a, 1, 0, n - 1);
    }

    // 更新 a[i] 为 mergeVal(a[i], val)
    // 时间复杂度 O(log n)
    public void update(int i, long val) {
        update(1, 0, n - 1, i, val);
    }

    // 返回用 mergeVal 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    // 时间复杂度 O(log n)
    public long query(int ql, int qr) {
        return query(1, 0, n - 1, ql, qr);
    }

    // 获取 a[i] 的值
    // 时间复杂度 O(log n)
    public long get(int i) {
        return query(1, 0, n - 1, i, i);
    }

    // 合并左右儿子的 val 到当前节点的 val
    private void maintain(int node) {
        tree[node] = mergeVal(tree[node * 2], tree[node * 2 + 1]);
    }

    // 用 a 初始化线段树
    // 时间复杂度 O(n)
    private void build(long[] a, int node, int l, int r) {
        if (l == r) { // 叶子
            tree[node] = a[l]; // 初始化叶节点的值
            return;
        }
        int m = (l + r) >>> 1;
        build(a, node * 2, l, m); // 初始化左子树
        build(a, node * 2 + 1, m + 1, r); // 初始化右子树
        maintain(node);
    }

    private void update(int node, int l, int r, int i, long val) {
        if (l == r) { // 叶子（到达目标）
            // 如果想直接替换的话，可以写 tree[node] = val
            tree[node] = mergeVal(tree[node], val);
            return;
        }
        int m = (l + r) >>> 1;
        if (i <= m) { // i 在左子树
            update(node * 2, l, m, i, val);
        } else { // i 在右子树
            update(node * 2 + 1, m + 1, r, i, val);
        }
        maintain(node);
    }

    private long query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node];
        }
        int m = (l + r) >>> 1;
        if (qr <= m) { // [ql, qr] 与右子树无交集，仅需递归左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 与左子树无交集，仅需递归右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        long lRes = query(node * 2, l, m, ql, qr);
        long rRes = query(node * 2 + 1, m + 1, r, ql, qr);
        return mergeVal(lRes, rRes);
    }
}

cpp

// 模板来源 ./09-常用数据结构
// 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
// 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
// 区间的下标：从 0 开始
template<typename T>
class SegmentTree {
    // 注：也可以去掉 template<typename T>，改在这里定义 T
    // using T = pair<int, int>;

    int n;
    vector<T> tree;

    // 合并两个 val
    T merge_val(T a, T b) const {
        return max(a, b); // **根据题目修改**
    }

    // 合并左右儿子的 val 到当前节点的 val
    void maintain(int node) {
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    // 用 a 初始化线段树
    // 时间复杂度 O(n)
    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) { // 叶子
            tree[node] = a[l]; // 初始化叶节点的值
            return;
        }
        int m = (l + r) >> 1;
        build(a, node * 2, l, m); // 初始化左子树
        build(a, node * 2 + 1, m + 1, r); // 初始化右子树
        maintain(node);
    }

    void update(int node, int l, int r, int i, T val) {
        if (l == r) { // 叶子（到达目标）
            // 如果想直接替换的话，可以写 tree[node] = val
            tree[node] = merge_val(tree[node], val);
            return;
        }
        int m = (l + r) >> 1;
        if (i <= m) { // i 在左子树
            update(node * 2, l, m, i, val);
        } else { // i 在右子树
            update(node * 2 + 1, m + 1, r, i, val);
        }
        maintain(node);
    }

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node];
        }
        int m = (l + r) >> 1;
        if (qr <= m) { // [ql, qr] 与右子树无交集，仅需递归左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 与左子树无交集，仅需递归右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }

public:
    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    // 线段树维护数组 a
    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) {
        build(a, 1, 0, n - 1);
    }

    // 更新 a[i] 为 merge_val(a[i], val)
    // 时间复杂度 O(log n)
    void update(int i, T val) {
        update(1, 0, n - 1, i, val);
    }

    // 返回用 merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    // 时间复杂度 O(log n)
    T query(int ql, int qr) const {
        return query(1, 0, n - 1, ql, qr);
    }

    // 获取 a[i] 的值
    // 时间复杂度 O(log n)
    T get(int i) const {
        return query(1, 0, n - 1, i, i);
    }
};

int main() {
    SegmentTree t(8, 0LL); // 如果这里写 0LL，那么 SegmentTree 存储的就是 long long 数据
    t.update(0, 1LL << 60);
    cout << t.query(0, 7) << endl;

    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    // 注意：如果要让 SegmentTree 存储 long long 数据，需要传入 vector<long long>
    SegmentTree t2(nums); // 这里 SegmentTree 存储的是 int 数据
    cout << t2.query(0, 7) << endl;
    return 0;
}

// 模板来源 ./09-常用数据结构
// 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
// 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
// 区间的下标：从 0 开始
type seg []struct {
    val int // **根据题目修改**
}

// 合并两个 val
func (seg) mergeVal(a, b int) int {
    return max(a, b) // **根据题目修改**
}

// 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 initVal
func newSegmentTree(n int, initVal int) seg {
    a := make([]int, n)
    for i := range a {
        a[i] = initVal
    }
    return newSegmentTreeWithArray(a)
}

// 线段树维护数组 a
func newSegmentTreeWithArray(a []int) seg {
    n := len(a)
    t := make(seg, 2<<bits.Len(uint(n-1)))
    t.build(a, 1, 0, n-1)
    return t
}

// 合并左右儿子的 val 到当前节点的 val
func (t seg) maintain(node int) {
    t[node].val = t.mergeVal(t[node*2].val, t[node*2+1].val)
}

// 用 a 初始化线段树
// 时间复杂度 O(n)
func (t seg) build(a []int, node, l, r int) {
    if l == r { // 叶子
        t[node].val = a[l] // 初始化叶节点的值
        return
    }
    m := (l + r) >> 1
    t.build(a, node*2, l, m) // 初始化左子树
    t.build(a, node*2+1, m+1, r) // 初始化右子树
    t.maintain(node)
}

// 更新 a[i] 为 mergeVal(a[i], val)
// 调用 t.update(1, 0, n-1, i, val)
// 0 <= i <= n-1
// 时间复杂度 O(log n)
func (t seg) update(node, l, r, i int, val int) {
    if l == r { // 叶子（到达目标）
        // 如果想直接替换的话，可以写 t[o].val = val
        t[node].val = t.mergeVal(t[node].val, val)
        return
    }
    m := (l + r) >> 1
    if i <= m { // i 在左子树
        t.update(node*2, l, m, i, val)
    } else { // i 在右子树
        t.update(node*2+1, m+1, r, i, val)
    }
    t.maintain(node)
}

// 返回用 mergeVal 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
// 调用 t.query(1, 0, n-1, ql, qr)
// 如果只想获取 a[i]，可以调用 t.query(1, 0, n-1, i, i)
// 0 <= ql <= qr <= n-1
// 时间复杂度 O(log n)
func (t seg) query(node, l, r, ql, qr int) int {
    if ql <= l && r <= qr { // 当前子树完全在 [ql, qr] 内
        return t[node].val
    }
    m := (l + r) >> 1
    if qr <= m { // [ql, qr] 与右子树无交集，仅需递归左子树
        return t.query(node*2, l, m, ql, qr)
    }
    if ql > m { // [ql, qr] 与左子树无交集，仅需递归右子树
        return t.query(node*2+1, m+1, r, ql, qr)
    }
    // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
    lRes := t.query(node*2, l, m, ql, qr)
    rRes := t.query(node*2+1, m+1, r, ql, qr)
    return t.mergeVal(lRes, rRes)
}

思维扩展：

§8.4 Lazy 线段树（有区间更新）

把任意区间用 $O (\log n)$ 个区间表示，线段树的每个节点记录对应区间的信息。

询问：把询问区间拆分成 $O (\log n)$ 个区间，对应着线段树的 $O (\log n)$ 个节点，把这 $O (\log n)$ 个节点的信息合并，即为答案。
区间更新：仍然是拆分成 $O (\log n)$ 个区间，对应着线段树的 $O (\log n)$ 个节点。但对于其中的非叶节点，不把更新的内容往下传递给子节点，而是记录「发生了更新，内容为 xxx」，把更新的内容记录下来。直到后续的询问或更新操作，需要访问或修改更下面的子节点信息时，才把更新的内容往下传。

基础模板代码如下。为方便入门理解，我没有做复杂封装。更通用的写法可以参考 AtCoder Library 的 lazysegtree.hpp。

# 模板来源 ./09-常用数据结构
class Node:
    __slots__ = 'val', 'todo'

class LazySegmentTree:
    # 懒标记初始值
    _TODO_INIT = 0  # **根据题目修改**

    def __init__(self, arr, default=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
        # arr 可以是 list 或者 int
        # 如果 arr 是 int，视作数组大小，默认值为 default
        if isinstance(arr, int):
            arr = [default] * arr
        n = len(arr)
        self._n = n
        self._tree = [Node() for _ in range(2 << (n - 1).bit_length())]
        self._build(arr, 1, 0, n - 1)

    # 合并两个 val
    def _merge_val(self, a: int, b: int) -> int:
        return a + b  # **根据题目修改**

    # 合并两个懒标记
    def _merge_todo(self, a: int, b: int) -> int:
        return a + b  # **根据题目修改**

    # 把懒标记作用到 node 子树（本例为区间加）
    def _apply(self, node: int, l: int, r: int, todo: int) -> None:
        cur = self._tree[node]
        # 计算 tree[node] 区间的整体变化
        cur.val += todo * (r - l + 1)  # **根据题目修改**
        cur.todo = self._merge_todo(todo, cur.todo)

    # 把当前节点的懒标记下传给左右儿子
    def _spread(self, node: int, l: int, r: int) -> None:
        todo = self._tree[node].todo
        if todo == self._TODO_INIT:  # 没有需要下传的信息
            return
        m = (l + r) // 2
        self._apply(node * 2, l, m, todo)
        self._apply(node * 2 + 1, m + 1, r, todo)
        self._tree[node].todo = self._TODO_INIT  # 下传完毕

    # 合并左右儿子的 val 到当前节点的 val
    def _maintain(self, node: int) -> None:
        self._tree[node].val = self._merge_val(self._tree[node * 2].val, self._tree[node * 2 + 1].val)

    # 用 a 初始化线段树
    # 时间复杂度 O(n)
    def _build(self, a: List[int], node: int, l: int, r: int) -> None:
        self._tree[node].todo = self._TODO_INIT
        if l == r:  # 叶子
            self._tree[node].val = a[l]  # 初始化叶节点的值
            return
        m = (l + r) // 2
        self._build(a, node * 2, l, m)  # 初始化左子树
        self._build(a, node * 2 + 1, m + 1, r)  # 初始化右子树
        self._maintain(node)

    def _update(self, node: int, l: int, r: int, ql: int, qr: int, f: int) -> None:
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内
            self._apply(node, l, r, f)
            return
        self._spread(node, l, r)
        m = (l + r) // 2
        if ql <= m:  # 更新左子树
            self._update(node * 2, l, m, ql, qr, f)
        if qr > m:  # 更新右子树
            self._update(node * 2 + 1, m + 1, r, ql, qr, f)
        self._maintain(node)

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内
            return self._tree[node].val
        self._spread(node, l, r)
        m = (l + r) // 2
        if qr <= m:  # [ql, qr] 与右子树无交集，仅需递归左子树
            return self._query(node * 2, l, m, ql, qr)
        if ql > m:  # [ql, qr] 与左子树无交集，仅需递归右子树
            return self._query(node * 2 + 1, m + 1, r, ql, qr)
        # [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        l_res = self._query(node * 2, l, m, ql, qr)
        r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
        return self._merge_val(l_res, r_res)

    # 用 f 更新 [ql, qr] 中的每个 a[i]
    # 0 <= ql <= qr <= n-1
    # 时间复杂度 O(log n)
    def update(self, ql: int, qr: int, f: int) -> None:
        self._update(1, 0, self._n - 1, ql, qr, f)

    # 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    # 0 <= ql <= qr <= n-1
    # 时间复杂度 O(log n)
    def query(self, ql: int, qr: int) -> int:
        return self._query(1, 0, self._n - 1, ql, qr)

java

// 模板来源 ./09-常用数据结构
class LazySegmentTree {
    // 懒标记初始值
    private static final long TODO_INIT = 0; // **根据题目修改**

    private static final class Node {
        long val; // **根据题目修改**
        long todo;
    }

    // 合并两个 val
    private long mergeVal(long a, long b) {
        return a + b; // **根据题目修改**
    }

    // 合并两个懒标记
    private long mergeTodo(long a, long b) {
        return a + b; // **根据题目修改**
    }

    // 把懒标记作用到 node 子树（本例为区间加）
    private void apply(int node, int l, int r, long todo) {
        Node cur = tree[node];
        // 计算 tree[node] 区间的整体变化
        cur.val += todo * (r - l + 1); // **根据题目修改**
        cur.todo = mergeTodo(todo, cur.todo);
    }

    private final int n;
    private final Node[] tree;

    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 initVal
    public LazySegmentTree(int n, long initVal) {
        this.n = n;
        long[] a = new long[n];
        Arrays.fill(a, initVal);
        tree = new Node[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        build(a, 1, 0, n - 1);
    }

    // 线段树维护数组 a
    public LazySegmentTree(long[] a) {
        n = a.length;
        tree = new Node[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        build(a, 1, 0, n - 1);
    }

    // 用 f 更新 [ql, qr] 中的每个 a[i]
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    public void update(int ql, int qr, long f) {
        update(1, 0, n - 1, ql, qr, f);
    }

    // 返回用 mergeVal 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    public long query(int ql, int qr) {
        return query(1, 0, n - 1, ql, qr);
    }

    // 把当前节点的懒标记下传给左右儿子
    private void spread(int node, int l, int r) {
        long todo = tree[node].todo;
        if (todo == TODO_INIT) { // 没有需要下传的信息
            return;
        }
        int m = (l + r) >>> 1;
        apply(node * 2, l, m, todo);
        apply(node * 2 + 1, m + 1, r, todo);
        tree[node].todo = TODO_INIT; // 下传完毕
    }

    // 合并左右儿子的 val 到当前节点的 val
    private void maintain(int node) {
        tree[node].val = mergeVal(tree[node * 2].val, tree[node * 2 + 1].val);
    }

    // 用 a 初始化线段树
    // 时间复杂度 O(n)
    private void build(long[] a, int node, int l, int r) {
        tree[node] = new Node();
        tree[node].todo = TODO_INIT;
        if (l == r) { // 叶子
            tree[node].val = a[l]; // 初始化叶节点的值
            return;
        }
        int m = (l + r) >>> 1;
        build(a, node * 2, l, m); // 初始化左子树
        build(a, node * 2 + 1, m + 1, r); // 初始化右子树
        maintain(node);
    }

    private void update(int node, int l, int r, int ql, int qr, long f) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            apply(node, l, r, f);
            return;
        }
        spread(node, l, r);
        int m = (l + r) >>> 1;
        if (ql <= m) { // 更新左子树
            update(node * 2, l, m, ql, qr, f);
        }
        if (qr > m) { // 更新右子树
            update(node * 2 + 1, m + 1, r, ql, qr, f);
        }
        maintain(node);
    }

    private long query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node].val;
        }
        spread(node, l, r);
        int m = (l + r) >>> 1;
        if (qr <= m) { // [ql, qr] 与右子树无交集，仅需递归左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 与左子树无交集，仅需递归右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        long lRes = query(node * 2, l, m, ql, qr);
        long rRes = query(node * 2 + 1, m + 1, r, ql, qr);
        return mergeVal(lRes, rRes);
    }
}

cpp

// 模板来源 ./09-常用数据结构
template<typename T, typename F>
class LazySegmentTree {
    // 注：也可以去掉 template<typename T, typename F>，改在这里定义 T 和 F
    // using T = pair<int, int>;
    // using F = pair<int, int>;

    // 懒标记初始值
    const F TODO_INIT = 0; // **根据题目修改**

    struct Node {
        T val;
        F todo;
    };

    int n;
    vector<Node> tree;

    // 合并两个 val
    T merge_val(const T& a, const T& b) const {
        return a + b; // **根据题目修改**
    }

    // 合并两个懒标记
    F merge_todo(const F& a, const F& b) const {
        return a + b; // **根据题目修改**
    }

    // 把懒标记作用到 node 子树（本例为区间加）
    void apply(int node, int l, int r, F todo) {
        Node& cur = tree[node];
        // 计算 tree[node] 区间的整体变化
        cur.val += todo * (r - l + 1); // **根据题目修改**
        cur.todo = merge_todo(todo, cur.todo);
    }

    // 把当前节点的懒标记下传给左右儿子
    void spread(int node, int l, int r) {
        Node& cur = tree[node];
        F todo = cur.todo;
        if (todo == TODO_INIT) { // 没有需要下传的信息
            return;
        }
        int m = (l + r) >> 1;
        apply(node * 2, l, m, todo);
        apply(node * 2 + 1, m + 1, r, todo);
        cur.todo = TODO_INIT; // 下传完毕
    }

    // 合并左右儿子的 val 到当前节点的 val
    void maintain(int node) {
        tree[node].val = merge_val(tree[node * 2].val, tree[node * 2 + 1].val);
    }

    // 用 a 初始化线段树
    // 时间复杂度 O(n)
    void build(const vector<T>& a, int node, int l, int r) {
        Node& cur = tree[node];
        cur.todo = TODO_INIT;
        if (l == r) { // 叶子
            cur.val = a[l]; // 初始化叶节点的值
            return;
        }
        int m = (l + r) >> 1;
        build(a, node * 2, l, m); // 初始化左子树
        build(a, node * 2 + 1, m + 1, r); // 初始化右子树
        maintain(node);
    }

    void update(int node, int l, int r, int ql, int qr, F f) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            apply(node, l, r, f);
            return;
        }
        spread(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) { // 更新左子树
            update(node * 2, l, m, ql, qr, f);
        }
        if (qr > m) { // 更新右子树
            update(node * 2 + 1, m + 1, r, ql, qr, f);
        }
        maintain(node);
    }

    T query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            return tree[node].val;
        }
        spread(node, l, r);
        int m = (l + r) >> 1;
        if (qr <= m) { // [ql, qr] 与右子树无交集，仅需递归左子树
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 与左子树无交集，仅需递归右子树
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }

public:
    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
    LazySegmentTree(int n, T init_val = 0) : LazySegmentTree(vector<T>(n, init_val)) {}

    // 线段树维护数组 a
    LazySegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) {
        build(a, 1, 0, n - 1);
    }

    // 用 f 更新 [ql, qr] 中的每个 a[i]
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    void update(int ql, int qr, F f) {
        update(1, 0, n - 1, ql, qr, f);
    }

    // 返回用 merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    T query(int ql, int qr) {
        return query(1, 0, n - 1, ql, qr);
    }
};

int main() {
    LazySegmentTree<long long, long long> t(8); // 默认值为 0
    t.update(3, 5, 100);
    t.update(4, 6, 10);
    cout << t.query(0, 7) << endl;

    vector<long long> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    LazySegmentTree<long long, long long> t2(nums);
    t2.update(3, 5, 1);
    t2.update(4, 6, 1);
    cout << t2.query(0, 7) << endl;
    return 0;
}

// 模板来源 ./09-常用数据结构
// 懒标记初始值
const todoInit int = 0 // **根据题目修改**

type lazySeg []struct {
    val  int // **根据题目修改**
    todo int
}

// 合并两个 val
func (lazySeg) mergeVal(a, b int) int {
    return a + b // **根据题目修改**
}

// 合并两个懒标记
func (lazySeg) mergeTodo(a, b int) int {
    return a + b // **根据题目修改**
}

// 把懒标记作用到 node 子树（本例为区间加）
func (t lazySeg) apply(node, l, r int, todo int) {
    cur := &t[node]
    // 计算 tree[node] 区间的整体变化
    cur.val += todo * (r - l + 1) // **根据题目修改**
    cur.todo = t.mergeTodo(todo, cur.todo)
}

// 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 initVal
func newLazySegmentTree(n int, initVal int) lazySeg {
    a := make([]int, n)
    for i := range a {
        a[i] = initVal
    }
    return newLazySegmentTreeWithArray(a)
}

// 线段树维护数组 a
func newLazySegmentTreeWithArray(a []int) lazySeg {
    n := len(a)
    t := make(lazySeg, 2<<bits.Len(uint(n-1)))
    t.build(a, 1, 0, n-1)
    return t
}

// 把当前节点的懒标记下传给左右儿子
func (t lazySeg) spread(node, l, r int) {
    // 类似「断点续传」，接着完成之前没完成的下传任务
    todo := t[node].todo
    if todo == todoInit { // 没有需要下传的信息
        return
    }
    m := (l + r) >> 1
    t.apply(node*2, l, m, todo)
    t.apply(node*2+1, m+1, r, todo)
    t[node].todo = todoInit // 下传完毕
}

// 合并左右儿子的 val 到当前节点的 val
func (t lazySeg) maintain(node int) {
    t[node].val = t.mergeVal(t[node*2].val, t[node*2+1].val)
}

// 用 a 初始化线段树
// 时间复杂度 O(n)
func (t lazySeg) build(a []int, node, l, r int) {
    t[node].todo = todoInit
    if l == r { // 叶子
        t[node].val = a[l] // 初始化叶节点的值
        return
    }
    m := (l + r) >> 1
    t.build(a, node*2, l, m) // 初始化左子树
    t.build(a, node*2+1, m+1, r) // 初始化右子树
    t.maintain(node)
}

// 用 f 更新 [ql, qr] 中的每个 a[i]
// 调用 t.update(1, 0, n-1, ql, qr, f)
// 0 <= ql <= qr <= n-1
// 时间复杂度 O(log n)
func (t lazySeg) update(node, l, r, ql, qr int, f int) {
    if ql <= l && r <= qr { // 当前子树完全在 [ql, qr] 内
        t.apply(node, l, r, f)
        return
    }
    t.spread(node, l, r)
    m := (l + r) >> 1
    if ql <= m { // 更新左子树
        t.update(node*2, l, m, ql, qr, f)
    }
    if qr > m { // 更新右子树
        t.update(node*2+1, m+1, r, ql, qr, f)
    }
    t.maintain(node)
}

// 返回用 mergeVal 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
// 调用 t.query(1, 0, n-1, ql, qr)
// 0 <= ql <= qr <= n-1
// 时间复杂度 O(log n)
func (t lazySeg) query(node, l, r, ql, qr int) int {
    if ql <= l && r <= qr { // 当前子树完全在 [ql, qr] 内
        return t[node].val
    }
    t.spread(node, l, r)
    m := (l + r) >> 1
    if qr <= m { // [ql, qr] 与右子树无交集，仅需递归左子树
        return t.query(node*2, l, m, ql, qr)
    }
    if ql > m { // [ql, qr] 与左子树无交集，仅需递归右子树
        return t.query(node*2+1, m+1, r, ql, qr)
    }
    // [ql, qr] 与左右子树均有交集，分别递归，然后合并结果
    lRes := t.query(node*2, l, m, ql, qr)
    rRes := t.query(node*2+1, m+1, r, ql, qr)
    return t.mergeVal(lRes, rRes)
}

§8.5 动态开点线段树

部分题目也可以用珂朵莉树解决。

§8.6 可持久化线段树

3762. 使数组元素相等的最小操作次数 2497

§8.7 ST 表（Sparse Table）

ST 表支持区间最值查询（Range Minimum/Maximum Query，RMQ），但不支持修改。

优点是代码短，且查询的时间复杂度是 $O (1)$ 。所以作为补充内容，附在此处。

class SparseTable:
    # 时间复杂度 O(n * log n)
    def __init__(self, nums: List[int], op: Callable[[int, int], int]):
        n = len(nums)
        w = n.bit_length()
        st = [[0] * n for _ in range(w)]
        st[0] = nums[:]
        for i in range(1, w):
            for j in range(n - (1 << i) + 1):
                st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))])
        self.st = st
        self.op = op

    # [l, r) 左闭右开，下标从 0 开始
    # 返回 op(nums[l:r])
    # 时间复杂度 O(1)
    def query(self, l: int, r: int) -> int:
        k = (r - l).bit_length() - 1
        return self.op(self.st[k][l], self.st[k][r - (1 << k)])


# 使用方法举例
nums = [3, 1, 4, 1, 5, 9, 2, 6]
st = SparseTable(nums, max)
print(st.query(0, 5))  # max(nums[0:5]) = 5
print(st.query(1, 1))  # 错误：必须保证 l < r

java

class SparseTable {
    private final int[][] stMin;
    private final int[][] stMax;

    // 时间复杂度 O(n * log n)
    public SparseTable(int[] nums) {
        int n = nums.length;
        int w = 32 - Integer.numberOfLeadingZeros(n);
        stMin = new int[w][n];
        stMax = new int[w][n];

        for (int j = 0; j < n; j++) {
            stMin[0][j] = nums[j];
            stMax[0][j] = nums[j];
        }

        for (int i = 1; i < w; i++) {
            for (int j = 0; j <= n - (1 << i); j++) {
                stMin[i][j] = Math.min(stMin[i - 1][j], stMin[i - 1][j + (1 << (i - 1))]);
                stMax[i][j] = Math.max(stMax[i - 1][j], stMax[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    // [l, r) 左闭右开，下标从 0 开始
    // 必须保证 l < r
    // 时间复杂度 O(1)
    public int queryMin(int l, int r) {
        int k = 31 - Integer.numberOfLeadingZeros(r - l);
        return Math.min(stMin[k][l], stMin[k][r - (1 << k)]);
    }

    // [l, r) 左闭右开，下标从 0 开始
    // 必须保证 l < r
    // 时间复杂度 O(1)
    public int queryMax(int l, int r) {
        int k = 31 - Integer.numberOfLeadingZeros(r - l);
        return Math.max(stMax[k][l], stMax[k][r - (1 << k)]);
    }
}

cpp

class SparseTable {
    vector<vector<int>> st_min;
    vector<vector<int>> st_max;

public:
    // 时间复杂度 O(n * log n)
    SparseTable(const vector<int>& nums) {
        int n = nums.size();
        int w = bit_width((uint32_t) n);
        st_min.resize(w, vector<int>(n));
        st_max.resize(w, vector<int>(n));

        for (int j = 0; j < n; j++) {
            st_min[0][j] = nums[j];
            st_max[0][j] = nums[j];
        }

        for (int i = 1; i < w; i++) {
            for (int j = 0; j <= n - (1 << i); j++) {
                st_min[i][j] = min(st_min[i - 1][j], st_min[i - 1][j + (1 << (i - 1))]);
                st_max[i][j] = max(st_max[i - 1][j], st_max[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    // [l, r) 左闭右开，下标从 0 开始
    // 必须保证 l < r
    // 时间复杂度 O(1)
    int query_min(int l, int r) const {
        int k = bit_width((uint32_t) r - l) - 1;
        return min(st_min[k][l], st_min[k][r - (1 << k)]);
    }

    // [l, r) 左闭右开，下标从 0 开始
    // 必须保证 l < r
    // 时间复杂度 O(1)
    int query_max(int l, int r) const {
        int k = bit_width((uint32_t) r - l) - 1;
        return max(st_max[k][l], st_max[k][r - (1 << k)]);
    }
};

type sparseTable[T any] struct {
    st [][]T
    op func(T, T) T
}

// 时间复杂度 O(n * log n)
func newSparseTable[T any](nums []T, op func(T, T) T) sparseTable[T] {
    n := len(nums)
    w := bits.Len(uint(n))
    st := make([][]T, w)
    for i := range st {
        st[i] = make([]T, n)
    }
    copy(st[0], nums)
    for i := 1; i < w; i++ {
        for j := range n - 1<<i + 1 {
            st[i][j] = op(st[i-1][j], st[i-1][j+1<<(i-1)])
        }
    }
    return sparseTable[T]{st, op}
}

// [l, r) 左闭右开，下标从 0 开始
// 返回 op(nums[l:r])
// 时间复杂度 O(1)
func (s sparseTable[T]) query(l, r int) T {
    k := bits.Len(uint(r-l)) - 1
    return s.op(s.st[k][l], s.st[k][r-1<<k])
}

// 使用方法举例
func main() {
    nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
    st := newSparseTable(nums, func(a, b int) int { return max(a, b) })
    fmt.Println(st.query(0, 5)) // 5
    fmt.Println(st.query(1, 1)) // 错误：必须保证 l < r
}

二维 ST 表:

3933. 矩阵中的局部最大值 II 模板题

九、伸展树（Splay 树）

2296. 设计一个文本编辑器
3526. 范围异或查询与子数组反转（会员题）

十、根号算法

§10.1 分块

注：上面树状数组和线段树的题目，可以尝试用分块解决。例如 307. 区域和检索 - 数组可修改。

3943. 递增后的数对数量 2410

§10.2 根号分解（Sqrt Decomposition）

§10.3 莫队算法

属于离线算法的一种。

3636. 查询超过阈值频率最高元素 2451 回滚莫队
3590. 第 K 小的路径异或和 2646 做法不止一种
2846. 边权重均等查询树上莫队和边权范围无关的做法

§10.4 其他

3234. 统计 1 显著的字符串的数量 2557

专题：离线算法

通过改变回答询问的顺序，使问题更容易处理。

相应的，在线算法就是按照 $queries$ 的顺序一个一个处理。

编程能力强化训练

知道大概怎么做，但不好实现的题目。部分题目是模拟题。

Part A

另见本题单的「§3.5 表达式解析」。

Part B

Part C

关联题单

关于链表和二叉树的题目，见链表、树与回溯。
关于字符串算法，见字符串题单。

算法题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

零、常用枚举技巧 ​

§0.1 枚举右，维护左 ​

§0.1.1 基础 ​

§0.1.2 进阶 ​

§0.2 枚举中间 ​

§0.2.1 基础 ​

§0.2.2 进阶 ​

§0.3 遍历对角线 ​

一、前缀和 ​

§1.1 基础 ​

§1.2 前缀和与哈希表 ​

§1.3 距离和 ​

§1.4 状态压缩前缀和 ​

§1.5 进阶 ​

§1.6 二维前缀和 ​

二、差分 ​

§2.1 一维差分 ​

§2.1.1 基础 ​

§2.1.2 进阶 ​

§2.2 二维差分 ​

三、栈 ​

§3.1 基础 ​

§3.2 进阶 ​

§3.3 邻项消除 ​

§3.4 合法括号字符串（RBS） ​

§3.5 表达式解析 ​

§3.6 对顶栈 ​

§3.7 单调栈 ​

四、队列 ​

§4.1 基础 ​

§4.2 设计 ​

§4.3 双端队列 ​

§4.4 单调队列 ​

五、堆（优先队列） ​

§5.1 基础 ​

§5.2 进阶 ​

§5.3 第 K 小/大 ​

§5.4 重排元素 ​

零、常用枚举技巧

§0.1 枚举右，维护左

§0.1.1 基础

§0.1.2 进阶

§0.2 枚举中间

§0.2.1 基础

§0.2.2 进阶

§0.3 遍历对角线

一、前缀和

§1.1 基础

§1.2 前缀和与哈希表

§1.3 距离和

§1.4 状态压缩前缀和

§1.5 进阶

§1.6 二维前缀和

二、差分

§2.1 一维差分

§2.1.1 基础

§2.1.2 进阶

§2.2 二维差分

三、栈

§3.1 基础

§3.2 进阶

§3.3 邻项消除

§3.4 合法括号字符串（RBS）

§3.5 表达式解析

§3.6 对顶栈

§3.7 单调栈

四、队列

§4.1 基础

§4.2 设计

§4.3 双端队列

§4.4 单调队列

五、堆（优先队列）

§5.1 基础

§5.2 进阶

§5.3 第 K 小/大

§5.4 重排元素

§5.5 反悔堆

§5.6 懒删除堆

§5.7 对顶堆（动态第 K 小/大）

六、字典树（trie）

§6.1 基础

§6.2 进阶

§6.3 字典树优化 DP

§6.4 0-1 字典树（异或字典树）

七、并查集

§7.1 基础

§7.2 进阶

§7.3 中介并查集

§7.4 数组上的并查集

§7.5 区间并查集

§7.6 带权并查集（边权并查集）

八、树状数组和线段树

§8.1 树状数组

§8.2 逆序对

§8.3 线段树（无区间更新）

§8.4 Lazy 线段树（有区间更新）

§8.5 动态开点线段树

§8.6 可持久化线段树

§8.7 ST 表（Sparse Table）

九、伸展树（Splay 树）

十、根号算法

§10.1 分块

§10.2 根号分解（Sqrt Decomposition）

§10.3 莫队算法

§10.4 其他

专题：离线算法

编程能力强化训练

Part A

Part B

Part C

关联题单

算法题单