算法模板 - 数据结构

本文整理刷题中常用的数据结构模板，按难度递增排列：前缀和 → 树状数组 → ST 表 → 并查集 → 堆 → 线段树系列 → 缓存淘汰 → 高级技巧。

1. 前缀和与差分

1.1 一维前缀和

核心思想：预处理 sum[i] = a[0] + a[1] + ... + a[i-1]，则 sum[l..r] = sum[r+1] - sum[l]，O(1) 查询区间和。

def build_prefix(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def query(prefix, l, r):
    """查询 arr[l..r] 的和（闭区间）"""
    return prefix[r + 1] - prefix[l]

1.2 二维前缀和

公式：sum[i][j] = grid[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]

查询子矩形 [r1, c1] ~ [r2, c2] 的和：

result = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]

def build_prefix_2d(grid):
    m, n = len(grid), len(grid[0])
    sum = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            sum[i][j] = (grid[i-1][j-1] + sum[i-1][j] +
                         sum[i][j-1] - sum[i-1][j-1])
    return sum

def query_2d(sum, r1, c1, r2, c2):
    return (sum[r2][c2] - sum[r1-1][c2] -
            sum[r2][c1-1] + sum[r1-1][c1-1])

1.3 差分

差分是前缀和的逆运算。对区间 [l, r] 加 val，只需 d[l] += val, d[r+1] -= val，最后求一次前缀和还原。

def range_add_diff(arr, operations):
    """差分：对区间批量加值"""
    n = len(arr)
    diff = [0] * (n + 1)
    for l, r, val in operations:
        diff[l] += val
        if r + 1 <= n:
            diff[r + 1] -= val
    # 还原
    result = [0] * n
    result[0] = arr[0] + diff[0]
    for i in range(1, n):
        diff[i] += diff[i - 1]
        result[i] = arr[i] + diff[i]
    return result

---

2. 树状数组（Fenwick Tree）

树状数组是比线段树更轻量的数据结构，同样支持 O(log n) 的单点更新和前缀查询，但代码更短、常数更小。

2.1 核心原理：lowbit

lowbit(x) = x & (-x)，取 x 的二进制表示中最低位的 1。tree[i] 管辖的区间长度就是 lowbit(i)。

lowbit(6) = lowbit(110₂) = 10₂ = 2
lowbit(8) = lowbit(1000₂) = 1000₂ = 8

2.2 单点更新 + 前缀和查询

class BIT:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed

    def update(self, i: int, delta: int) -> None:
        """在位置 i 加上 delta"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i: int) -> int:
        """查询前缀和 [1, i]"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_query(self, l: int, r: int) -> int:
        return self.query(r) - self.query(l - 1)

为什么 O(log n)？ 更新时 i += lowbit(i) 跳到所有包含位置 i 的区间，共 log n 个。查询时 i -= lowbit(i) 跳到下一个需要累加的区间，共 log n 个。

2.3 区间修改 + 区间求和（双树状数组）

class BITRange:
    """双树状数组实现区间修改 + 区间求和"""
    def __init__(self, n: int):
        self.n = n
        self.b1 = BIT(n)
        self.b2 = BIT(n)

    def range_add(self, l: int, r: int, delta: int) -> None:
        self.b1.update(l, delta)
        self.b1.update(r + 1, -delta)
        self.b2.update(l, delta * l)
        self.b2.update(r + 1, -delta * (r + 1))

    def prefix_sum(self, i: int) -> int:
        return self.b1.query(i) * (i + 1) - self.b2.query(i)

    def range_sum(self, l: int, r: int) -> int:
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

---

3. ST 表（Sparse Table）

ST 表是处理静态区间最值查询的利器，预处理 O(n log n)，查询 O(1)。

3.1 核心原理：倍增

st[i][j] 表示从位置 i 开始、长度为 2^j 的区间内的最大值。

st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])

查询时，用两个长度为 2^k 的区间覆盖 [l, r]（可能有重叠，但不影响最值）。

class SparseTable:
    def __init__(self, data: list):
        n = len(data)
        k = n.bit_length()
        st = [[0] * n for _ in range(k)]
        st[0] = data[:]
        for j in range(1, k):
            for i in range(n - (1 << j) + 1):
                st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))])
        self.st = st
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i // 2] + 1

    def query(self, l: int, r: int) -> int:
        """查询 [l, r] 的最大值（闭区间）"""
        k = self.log[r - l + 1]
        return max(self.st[k][l], self.st[k][r - (1 << k) + 1])

ST 表 vs 线段树：

特性	ST 表	线段树
预处理	O(n log n)	O(n)
查询	O(1)	O(log n)
修改	不支持	O(log n)
适用场景	静态区间最值	动态修改 + 查询

---

4. 并查集（DSU）

并查集用于处理集合合并和元素归属查询，常用于图的连通性判断。

4.1 基本实现

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

路径压缩 + 按秩合并 使得单次操作的均摊复杂度为 O(α(n))，α 是反阿克曼函数，实际可视为常数（≤ 4）。

4.2 扩展并查集（AcWing 257 - 关押罪犯）

思路：用扩展并查集，enemy[i] 记录 i 的"敌人"。如果 a 和 b 有仇恨，就把 a 和 b 的敌人合并，b 和 a 的敌人合并——敌人的敌人是朋友。

class ExtDSU:
    def __init__(self, n):
        self.parent = list(range(2 * n + 1))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

# 用法：对每对仇恨 (a, b)：
#   union(a, b + n)  — a 和 b 的敌人是朋友
#   union(a + n, b)  — b 和 a 的敌人是朋友

---

5. 堆与对顶堆

5.1 懒删除堆

标准库的 heapq 不支持删除堆中间的元素。懒删除堆的做法是：先标记要删除的元素，等它弹出堆顶时再真正跳过。

import heapq
from collections import Counter

class LazyHeap:
    def __init__(self):
        self.heap = []
        self.deleted = Counter()

    def push(self, val):
        heapq.heappush(self.heap, val)

    def pop(self):
        while self.heap:
            val = heapq.heappop(self.heap)
            if self.deleted[val] > 0:
                self.deleted[val] -= 1
                continue
            return val
        raise IndexError("pop from empty heap")

    def remove(self, val):
        self.deleted[val] += 1

    def top(self):
        while self.heap and self.deleted[self.heap[0]] > 0:
            self.deleted[heapq.heappop(self.heap)] -= 1
        return self.heap[0]

5.2 对顶堆（动态中位数）

对顶堆是维护动态数据流中位数的经典结构：

• 大根堆存储较小的一半
• 小根堆存储较大的一半
• 保持大根堆的大小 = 小根堆的大小 或 大根堆的大小 = 小根堆的大小 + 1

import heapq

class MedianHeap:
    def __init__(self):
        self.small = []  # 大根堆（取负实现）
        self.large = []  # 小根堆

    def add(self, num):
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
        else:
            heapq.heappush(self.large, num)
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        elif len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def get_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2.0

---

6. 线段树（Segment Tree）

线段树是一种高效处理区间查询和单点/区间更新的树形结构，核心操作均为 O(log n)。

6.1 基本原理

线段树是一棵二叉树，每个节点代表一个区间。叶子节点代表单个元素，内部节点代表其左右子节点区间的合并结果。

         [0, 8)
       /        \
   [0, 4)      [4, 8)
   /    \      /    \
 [0,2) [2,4) [4,6) [6,8)
 / \   / \   / \   / \
 0  1  2  3  4  5  6  7

6.2 单点修改 + 区间查询

class SegmentTree:
    def __init__(self, data: list):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, pos: int, value: int) -> None:
        pos += self.size
        self.tree[pos] = value
        pos >>= 1
        while pos >= 1:
            new_val = self.tree[2 * pos] + self.tree[2 * pos + 1]
            if self.tree[pos] == new_val:
                break
            self.tree[pos] = new_val
            pos >>= 1

    def query(self, l: int, r: int) -> int:
        """查询 [l, r) 的和（左闭右开）"""
        res = 0
        l += self.size; r += self.size
        while l < r:
            if l & 1: res += self.tree[l]; l += 1
            if r & 1: r -= 1; res += self.tree[r]
            l >>= 1; r >>= 1
        return res

6.3 泛型线段树

将"求和"泛化为任意可结合运算（max、min、gcd 等）：

class GenericSegmentTree:
    def __init__(self, data, merge, neutral):
        self.n = len(data); self.merge = merge; self.neutral = neutral
        self.size = 1
        while self.size < self.n: self.size <<= 1
        self.tree = [neutral] * (2 * self.size)
        for i in range(self.n): self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = merge(self.tree[2*i], self.tree[2*i+1])

    def update(self, pos, value):
        pos += self.size; self.tree[pos] = value; pos >>= 1
        while pos >= 1:
            self.tree[pos] = self.merge(self.tree[2*pos], self.tree[2*pos+1])
            pos >>= 1

    def query(self, l, r):
        res_l = res_r = self.neutral
        l += self.size; r += self.size
        while l < r:
            if l & 1: res_l = self.merge(res_l, self.tree[l]); l += 1
            if r & 1: r -= 1; res_r = self.merge(self.tree[r], res_r)
            l >>= 1; r >>= 1
        return self.merge(res_l, res_r)

# 用法
st_max = GenericSegmentTree([3,1,4,1,5], merge=max, neutral=float('-inf'))
print(st_max.query(1, 4))  # max(1,4,1) = 4

---

7. 懒标记线段树

当需要对整个区间做加法/赋值操作时，需要引入懒标记（Lazy Propagation）。

核心思想：修改区间时，如果当前节点的区间完全被目标区间覆盖，就只在当前节点打标记，不往下递归。下次需要用到子节点时，再把标记"下推"。

class LazySegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n: self.size <<= 1
        self.tree = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        for i in range(self.n): self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def _apply(self, node, length, value):
        self.tree[node] += value * length
        self.lazy[node] += value

    def _push(self, node, length):
        if self.lazy[node]:
            self._apply(2*node, length//2, self.lazy[node])
            self._apply(2*node+1, length//2, self.lazy[node])
            self.lazy[node] = 0

    def _range_add(self, l, r, value, node, nl, nr):
        if r <= nl or nr <= l: return
        if l <= nl and nr <= r:
            self._apply(node, nr - nl, value); return
        self._push(node, nr - nl)
        mid = (nl + nr) // 2
        self._range_add(l, r, value, 2*node, nl, mid)
        self._range_add(l, r, value, 2*node+1, mid, nr)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def range_add(self, l, r, value):
        self._range_add(l, r, value, 1, 0, self.size)

    def _range_query(self, l, r, node, nl, nr):
        if r <= nl or nr <= l: return 0
        if l <= nl and nr <= r: return self.tree[node]
        self._push(node, nr - nl)
        mid = (nl + nr) // 2
        return (self._range_query(l, r, 2*node, nl, mid) +
                self._range_query(l, r, 2*node+1, mid, nr))

    def range_query(self, l, r):
        return self._range_query(l, r, 1, 0, self.size)

---

8. 动态开点线段树

当值域非常大（如 10^18）时，普通线段树开不下数组。动态开点只在需要时创建节点，空间 O(q log V)。

class Node:
    __slots__ = ['left', 'right', 'val']
    def __init__(self, val):
        self.left = None; self.right = None; self.val = val

class DynamicSegmentTree:
    def __init__(self, merge_func, neutral_val, min_range=-10**18, max_range=10**18):
        self.merge = merge_func
        self.neutral = neutral_val
        self.min_r = min_range; self.max_r = max_range
        self.root = Node(neutral_val)

    def _update(self, node, l, r, pos, value):
        if l == r: node.val = value; return
        mid = (l + r) // 2
        if pos <= mid:
            if not node.left: node.left = Node(self.neutral)
            self._update(node.left, l, mid, pos, value)
        else:
            if not node.right: node.right = Node(self.neutral)
            self._update(node.right, mid+1, r, pos, value)
        lv = node.left.val if node.left else self.neutral
        rv = node.right.val if node.right else self.neutral
        node.val = self.merge(lv, rv)

    def update(self, pos, value):
        self._update(self.root, self.min_r, self.max_r, pos, value)

    def _query(self, node, l, r, ql, qr):
        if not node or r < ql or l > qr: return self.neutral
        if ql <= l and r <= qr: return node.val
        mid = (l + r) // 2
        return self.merge(
            self._query(node.left, l, mid, ql, qr),
            self._query(node.right, mid+1, r, ql, qr))

    def query(self, l, r):
        return self._query(self.root, self.min_r, self.max_r,
                           max(l, self.min_r), min(r, self.max_r))

---

9. 权值树状数组

普通树状数组维护"位置 i 的值"，权值树状数组维护"值为 i 的元素出现次数"，可以做排名查询和第 k 小查询。

from math import inf

class BinaryIndexedMaxTree:
    """维护前缀最大值的树状数组"""
    __slots__ = ["n", "c"]
    def __init__(self, n):
        self.n = n; self.c = [-inf] * (n + 1)

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] = max(self.c[x], delta)
            x += x & -x

    def query(self, x):
        s = -inf
        while x > 0:
            s = max(s, self.c[x]); x -= x & -x
        return s

---

10. 前缀最大长度及计数（BIT 变种）

适用场景：动态维护前缀范围内的最大长度及其出现次数，常用于最长递增子序列计数问题。

class Fenwick:
    __slots__ = 'mx_length', 'mx_cnt'
    def __init__(self, n):
        self.mx_length = [0] * (n + 1)
        self.mx_cnt = [0] * (n + 1)

    def add(self, i, length, cnt):
        while i < len(self.mx_length):
            if self.mx_length[i] == length:
                self.mx_cnt[i] += cnt
            elif self.mx_length[i] < length:
                self.mx_cnt[i] = cnt; self.mx_length[i] = length
            i += i & -i

    def sum(self, i):
        length = cnt = 0
        while i > 0:
            if length == self.mx_length[i]: cnt += self.mx_cnt[i]
            elif length < self.mx_length[i]:
                cnt = self.mx_cnt[i]; length = self.mx_length[i]
            i -= i & -i
        return length, cnt

---

11. 离散化 + 二维差分

当坐标值很大但操作次数不多时，先离散化坐标再用差分处理：

def max_overlap_count(rectangles):
    xs = sorted({x for rect in rectangles for x in (rect[0], rect[2])})
    ys = sorted({y for rect in rectangles for y in (rect[1], rect[3])})
    x_id = {x: i for i, x in enumerate(xs)}
    y_id = {y: i for i, y in enumerate(ys)}

    diff = [[0] * (len(ys) + 1) for _ in range(len(xs) + 1)]
    for x1, y1, x2, y2 in rectangles:
        diff[x_id[x1]][y_id[y1]] += 1
        diff[x_id[x2]][y_id[y1]] -= 1
        diff[x_id[x1]][y_id[y2]] -= 1
        diff[x_id[x2]][y_id[y2]] += 1

    ans = 0
    for i in range(len(xs)):
        for j in range(len(ys)):
            if i > 0: diff[i][j] += diff[i-1][j]
            if j > 0: diff[i][j] += diff[i][j-1]
            if i > 0 and j > 0: diff[i][j] -= diff[i-1][j-1]
            ans = max(ans, diff[i][j])
    return ans

---

12. LRU / MRU 缓存淘汰

LRU 淘汰最久未使用的，MRU 淘汰最近使用的。基于 OrderedDict 实现，O(1) 操作。

from collections import OrderedDict

def lru_cache(sequence, capacity):
    cache = OrderedDict(); misses = hits = 0
    for ch in sequence:
        if ch in cache:
            cache.move_to_end(ch); hits += 1
        else:
            misses += 1; cache[ch] = True
            if len(cache) > capacity:
                cache.popitem(last=False)  # LRU：弹出最久未用的
    return misses, hits, list(cache.keys())

def mru_cache(sequence, capacity):
    cache = OrderedDict(); misses = hits = 0
    for ch in sequence:
        if ch in cache:
            cache.move_to_end(ch); hits += 1
        else:
            misses += 1; cache[ch] = True
            if len(cache) > capacity:
                cache.popitem(last=True)   # MRU：弹出最近使用的
    return misses, hits, list(cache.keys())

---

13. 跳表（Skip List）

跳表是一种概率平衡的数据结构，通过多层索引实现 O(log n) 的搜索/插入/删除。

from random import random

MAX_LEVEL = 32; P_FACTOR = 0.25

def random_level():
    lv = 1
    while lv < MAX_LEVEL and random() < P_FACTOR: lv += 1
    return lv

class SkiplistNode:
    __slots__ = 'val', 'forward'
    def __init__(self, val, max_level=MAX_LEVEL):
        self.val = val; self.forward = [None] * max_level

class Skiplist:
    def __init__(self):
        self.head = SkiplistNode(-1); self.level = 0

    def search(self, target):
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < target:
                cur = cur.forward[i]
        cur = cur.forward[0]
        return cur is not None and cur.val == target

    def add(self, num):
        update = [self.head] * MAX_LEVEL; cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] and cur.forward[i].val < num:
                cur = cur.forward[i]
            update[i] = cur
        lv = random_level()
        self.level = max(self.level, lv)
        new_node = SkiplistNode(num, lv)
        for i in range(lv):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def erase(self, num):
        update = [None] * MAX_LEVEL; cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] and cur.forward[i].val < num:
                cur = cur.forward[i]
            update[i] = cur
        cur = cur.forward[0]
        if cur is None or cur.val != num: return False
        for i in range(self.level):
            if update[i].forward[i] != cur: break
            update[i].forward[i] = cur.forward[i]
        while self.level > 1 and self.head.forward[self.level-1] is None:
            self.level -= 1
        return True

---

14. 维护前 k 大

from sortedcontainers import SortedList

class TopKMaintainer:
    def __init__(self, k):
        self.k = k
        self.upper = SortedList()  # 前 k 大
        self.lower = SortedList()  # 其余

    def add(self, x):
        if len(self.upper) < self.k:
            self.upper.add(x)
        elif x > self.upper[0]:
            self.lower.add(self.upper.pop(0))
            self.upper.add(x)
        else:
            self.lower.add(x)

    def remove(self, x):
        if x in self.upper:
            self.upper.remove(x)
            if self.lower: self.upper.add(self.lower.pop())
        else:
            self.lower.remove(x)

    def get_top_k(self):
        return list(self.upper)

---

15. 莫队算法

莫队是一种离线处理区间查询的算法。核心思想是将所有查询按"块"排序，然后用两个指针滑动，均摊 O(√n) 次移动。

import math
from collections import defaultdict

def mo_query(arr, queries):
    n, q = len(arr), len(queries)
    block_size = int(math.sqrt(n)) + 1
    sorted_queries = [(queries[i][0], queries[i][1], i) for i in range(q)]
    # 偶奇排序优化
    sorted_queries.sort(key=lambda x: (
        x[0] // block_size,
        x[1] if (x[0] // block_size) % 2 == 0 else -x[1]
    ))

    current_l, current_r = 0, -1
    freq = defaultdict(int); distinct_count = 0
    result = [0] * q

    for l, r, idx in sorted_queries:
        while current_l > l:
            current_l -= 1
            if freq[arr[current_l]] == 0: distinct_count += 1
            freq[arr[current_l]] += 1
        while current_l < l:
            freq[arr[current_l]] -= 1
            if freq[arr[current_l]] == 0: distinct_count -= 1
            current_l += 1
        while current_r < r:
            current_r += 1
            if freq[arr[current_r]] == 0: distinct_count += 1
            freq[arr[current_r]] += 1
        while current_r > r:
            freq[arr[current_r]] -= 1
            if freq[arr[current_r]] == 0: distinct_count -= 1
            current_r -= 1
        result[idx] = distinct_count
    return result

偶奇排序优化：左端点在偶数块时右端点升序，在奇数块时右端点降序。这样右指针不需要每次都从头滑到尾。

---

16. 回滚莫队

普通莫队在"添加容易、删除困难"的场景下不好用。回滚莫队的做法是：只做添加操作，需要"删除"时直接回滚到上一个块的右边界。

def rollback_mo(nums, queries):
    n, m = len(nums), len(queries)
    cnt = defaultdict(int)
    max_cnt = min_val = 0

    def add(x):
        nonlocal max_cnt, min_val
        cnt[x] += 1
        if cnt[x] > max_cnt: max_cnt, min_val = cnt[x], x
        elif cnt[x] == max_cnt: min_val = min(min_val, x)

    ans = [-1] * m
    block_size = ceil(n / sqrt(m))
    qs = []
    for i, (l, r, threshold) in enumerate(queries):
        if r - l + 1 > block_size:
            qs.append((l // block_size, l, r, threshold, i))
            continue
        for x in nums[l:r+1]: add(x)
        if max_cnt >= threshold: ans[i] = min_val
        cnt.clear(); max_cnt = 0

    qs.sort(key=lambda q: (q[0], q[2]))
    for i, (bid, ql, qr, threshold, qid) in enumerate(qs):
        l0 = (bid + 1) * block_size
        if i == 0 or bid > qs[i-1][0]:
            r = l0; cnt.clear(); max_cnt = 0
        while r <= qr: add(nums[r]); r += 1
        tmp_max, tmp_min = max_cnt, min_val
        for x in nums[ql:l0]: add(x)
        if max_cnt >= threshold: ans[qid] = min_val
        max_cnt, min_val = tmp_max, tmp_min
        for x in nums[ql:l0]: cnt[x] -= 1
    return ans

---

17. 滑动窗口中位数（双堆 + 懒删除）

class LazyHeap2:
    def __init__(self):
        self.hq = []; self.cnt = defaultdict(int); self.size = 0
    def push(self, num):
        if self.cnt[num] > 0: self.cnt[num] -= 1
        else: heappush(self.hq, num)
        self.size += 1
    def remove(self, num): self.size -= 1; self.cnt[num] += 1
    def real_remove(self):
        while self.hq and self.cnt[self.hq[0]] > 0:
            self.cnt[self.hq[0]] -= 1; heappop(self.hq)
    def top(self): self.real_remove(); return self.hq[0]
    def pop(self): self.size -= 1; self.real_remove(); return heappop(self.hq)

def median_sliding_window(nums, k):
    ans = []; upper = LazyHeap2(); lower = LazyHeap2()
    for i, v in enumerate(nums):
        if upper.size == lower.size:
            lower.push(-upper.pushpop(v) if upper.size > 0 else v)
        else:
            upper.push(-lower.pushpop(-v) if lower.size > 0 else v)
        if i < k - 1: continue
        if k & 1: ans.append(float(-lower.top()))
        else: ans.append((upper.top() - lower.top()) / 2.0)
        del_num = nums[i - k + 1]
        if -lower.top() >= del_num:
            lower.remove(-del_num)
            if lower.size < upper.size: lower.push(-upper.pop())
        else:
            upper.remove(del_num)
            if lower.size > upper.size + 1: upper.push(-lower.pop())
    return ans

---

总结

数据结构	单点修改	区间查询	区间修改	适用场景
前缀和	—	O(1)	O(n)	静态区间求和
树状数组	O(log n)	O(log n)（前缀）	O(log n)（双BIT）	轻量，前缀操作为主
ST 表	不支持	O(1)	不支持	静态区间最值
并查集	—	—	O(α(n))合并	集合合并、连通性
堆（懒删除）	O(log n)	O(1)堆顶	—	需要删除堆中间元素
对顶堆	O(log n)	O(1)中位数	—	动态中位数
线段树	O(log n)	O(log n)	O(log n)	万能，动态区间操作
动态开点线段树	O(log V)	O(log V)	—	值域极大（10^18）
权值树状数组	O(log n)	O(log n)	—	排名查询、第k小
前缀最大长度BIT	O(log n)	O(log n)	—	LIS 计数问题
LRU / MRU	O(1)	O(1)	—	缓存淘汰策略
跳表	O(log n)	O(log n)	—	概率平衡有序集合
维护前k大	O(log n)	O(1)	—	动态前k大
莫队	—	O((n+q)√n)	—	离线区间查询
回滚莫队	—	O((n+q)√n)	—	添加容易删除困难

模板源码：AlgorithmLearning