Range tree
(Mylib/DataStructure/RangeTree/range_tree.cpp)
Operations
-
add(int x, int y)
-
build()
-
RangeTree
を構築する。
- Time complexity $O(N \log N)$
-
get(int sx, int sy, int tx, int ty)
-
[sx, tx), [sy, ty)
内の点を列挙する。
- Time complexity $O(\log^2 N + K)$
Requirements
-
build
は唯一回だけ呼び出される。
- 必ず
add
, build
, get
の順で実行する。
Notes
Problems
References
Verified with
Code
Back to top page