数据结构

数据结构

高效的数据结构是优化算法的关键。共 12 个模板。

← 返回模板库

9.1前缀和 - 一维

O(1) 查询区间和

O(n) 预处理, O(1) 查询

9.2前缀和 - 二维

O(1) 查询子矩阵和

O(nm) 预处理, O(1) 查询

9.3差分 - 一维

区间加操作转为单点修改

O(1) 修改, O(n) 还原

9.4差分 - 二维

子矩阵加操作转为四个角点修改

O(1) 修改, O(nm) 还原

9.5树状数组

支持单点修改 + 区间查询的轻量级数据结构

O(log n)

9.6树状数组 - 区间修改

差分树状数组，支持区间加 + 单点查询

O(log n)

9.7线段树 - 单点修改

支持单点修改 + 区间查询

O(log n)

9.8线段树 - 区间修改（懒标记）

懒惰传播，区间加 + 区间查询

O(log n)

9.9ST 表（Sparse Table）

静态区间最值查询

O(n log n) 预处理, O(1) 查询

9.10LCA - 倍增法

二进制跳转求最近公共祖先

O(n log n) 预处理, O(log n) 查询

9.11树上差分

路径上的权值修改转为端点修改

O(log n) 修改 (配合 LCA)

9.12权值线段树

以值域建树，求第 k 小、排名等

O(log n)