004-数据结构-二维树状数组

核心概述：二维树状数组支持二维前缀和查询与单点增量更新，需预先登记将被更新的点以完成离散化与建树，查询与更新均为 O(log^2 N)。

原文引述：

Description: Computes sums a[i,j] for all i<I, j<J, and increases single elements a[i,j]. Requires that the elements to be updated are known in advance (call fakeUpdate() before init()). Time: $O({\log }^{2}N)$. (Use persistent segment trees for $O(\log N)$.) Status: stress-tested

展开阐述：

• 定义与问题背景、适用场景
  • 在二维网格上维护点权，支持矩形前缀 [0..x) × [0..y) 的求和与单点加法更新；常用于二维计数、二维离线统计、子矩形和等问题。
  • 相较一维 003-数据结构-树状数组，在外层 x 上再嵌套一棵“按 y 离散化的一维树状数组”。
• 接口与数据结构字段
  • 成员：
    • ys：vector<vector>，每个外层 BIT 节点存其覆盖范围内参与更新的所有 y 坐标列表。
    • ft：vector，与 ys 一一对应的内层一维树状数组（FT）。
  • 方法：
    • fakeUpdate(x, y)：预登记所有将来会 update 的 (x,y)，沿 x 的 BIT 父链把 y 推入对应 ys[x]；为坐标离散化与尺寸分配做准备。
    • init()：对每个 ys[x] 排序去重，并用其长度构造对应的 ft[x]。
    • update(x, y, dif)：沿 x 的外层 BIT 逐层向上，在每层利用 ind(x,y) 将 y 映射到离散索引并在 ft[x] 上执行一维 update。
    • query(x, y)：返回区域 [0,x)×[0,y) 的和；沿 x 的外层链向上累加，每层用 ind(x-1,y) 在内层 ft 取前缀。
  • 工具：
    • ind(x, y)：在 ys[x] 中对 y 执行 lower_bound，得到离散化后的索引。
• 核心算法流程/要点
  • 预处理：
    • 对所有更新点先调用 fakeUpdate(x,y)，再统一调用 init() 完成 ys 的排序去重与 ft 的创建。
  • 单点更新：
    • for (; x < sz(ys); x |= x + 1) ft[x].update(ind(x, y), dif)。
  • 前缀查询：
    • for (; x; x &= x - 1) res += ft[x-1].query(ind(x-1, y))。
• 复杂度与边界条件
  • 单点更新与二维前缀和查询均为 O(log^2 N)。
  • 必须提前知道所有会被更新的点；若在线产生新点，需扩展结构或改用其他数据结构（如持久化线段树可达 O(log N)）。
  • y 必须在各自 ys[x] 的范围内出现；缺少 fakeUpdate 会导致 ind 定位失败。
• 实现细节与坑
  • 坐标离散化按每个外层节点独立进行，务必在 init 前填充完整点集。
  • query 与 update 的 x 循环方向一个向下（x&=x-1）、一个向上（x|=x+1），注意 off-by-one。
  • ind 使用 lower_bound，要求 ys[x] 已排序且去重。
• 变体/扩展
  • 若需要一般子矩形和 [x1,x2)×[y1,y2)，可用四个前缀和相减。
  • 若更新与查询更复杂或需在线扩容，可考虑 012-数据结构-线段树 或持久化线段树替代。
• 正确性要点
  • 不变式：每个外层节点的内层 FT 维护其覆盖 x 范围内、对应 ys[x] 离散坐标上的点权累计；两层累加保证二维前缀的叠加法则成立。

关联节点

• 003-数据结构-树状数组
• 012-数据结构-线段树
• 013-数据结构-子矩阵