Module dynamic_segment_tree_2d

Source
Expand description

2D dynamic segment tree(implicit,交互 2 分木 + split 軸キャッシュ)

方針:

  • 本体 API は apply(rx, ry, act)get_range(rx, ry)
  • get(x, y)get_range(x..x+1, y..y+1) のラッパー
  • 重要:ノードごとに「このノードはどちらの軸で split するか」を 1 度だけ決めて保持する
    • クエリ依存の軸選択は「未決定ノードの初回 split 決定」にだけ使う
    • これにより left/right が表す領域の意味が常に一意になり,正しさが保たれる
  • split 不能(軸長 1)なら反転して試す,両方不能なら真の葉
  • ActedMonoidWithSize::e_with_size(len)len は「面積 area」とみなす

Structs§

DynamicSegmentTree2D