Sqrt Tree
(data-structure/sqrt_tree.hpp)
Description
Sqrt tree は,半群 $(T, \cdot)$ の静的な列の区間和を高速に計算するデータ構造である.平方分割を再帰的に行うことで木の高さを $O(\log\log n)$ にしている.Sparse table と比べて前処理が高速でメモリ使用量が少ないという特徴がある.
ここでは実装していないが,$O(\sqrt{N})$ で要素の更新も可能である.
空間計算量: $O(n\log\log n)$
Operations
-
SqrtTree(vector<T> v)
-
v
から sqrt tree を構築する
- 時間計算量: $O(n\log\log n)$
-
T fold(int l, int r)
- 区間 $[l, r)$ を fold する
- 時間計算量: $O(1)$
Reference
Verified with
Code
Back to top page