a/Library

History

Dushyant Singh 7761f38957 fix off by one in sparse table Given code fails for `query(0, n - 1)` Problem to test on https://codeforces.com/contest/1549/problem/D		2021-12-12 17:22:34 +05:30
..
dynamic_segment_tree.cpp	Update dynamic_segment_tree.cpp	2020-05-02 20:46:33 -05:00
dynamic_segment_tree_2d.cpp	New style	2020-09-06 14:27:14 -05:00
fenwick_tree.cpp	Update fenwick_tree.cpp	2021-01-19 21:44:08 -06:00
fenwick_tree_2d.cpp	Update fenwick_tree_2d.cpp	2020-06-26 11:51:11 -05:00
optimized_segment_tree.cpp	updating libraries	2019-09-03 21:43:14 -05:00
quadtree.cpp	Create quadtree.cpp	2019-07-26 11:16:10 -05:00
README.md	Update README.md	2020-06-02 21:44:36 -05:00
seg_fenwick_tree.cpp	New style	2020-09-06 14:27:14 -05:00
seg_ordered_set_tree.cpp	Use less instead of less_equal in ordered_set	2021-07-05 12:15:06 +05:30
segment_tree.cpp	More cleanup	2020-09-21 12:49:18 -05:00
sparse_table.cpp	fix off by one in sparse table	2021-12-12 17:22:34 +05:30
union-find_disjoint_set.cpp	Update union-find_disjoint_set.cpp	2020-09-05 17:17:25 -05:00

Complexity Table

Data Structure	Storage	Build	Point Update	Range Update	Point Query	Range Query
Segment Tree	O(n)	O(n)	O(log n)	O(log n)	O(log n)	O(log n)
Fenwick Tree	O(n)	O(n)	O(log n)	O(log n)	O(log n)	O(log n)
Sparse Table	O(n log n)	O(n log n)	-	-	O(1)	O(1)
Segment Tree (2D)	O(n²)	O(n)	O(log² n)	O(log² n)	O(log² n)	O(log² n)
Fenwick Tree (2D)	O(n²)	O(n)	O(log² n)	-	O(log² n)	O(log² n)
Quadtree	O(n²)	O(n)	O(log n)	O(log n)	O(log n)	O(n)