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) |
| Sparse Table | O(n log n) | O(n log n) | - | - | O(1) | O(1) |
| Segment Tree (2D) | O(n2) | O(n) | O(log2 n) | O(log2 n) | O(log2 n) | O(log2 n) |
| Fenwick Tree (2D) | O(n2) | O(n) | O(log2 n) | - | O(log2 n) | O(log2 n) |
| Quadtree | O(n2) | O(n) | O(log n) | O(log n) | O(log n) | O(n) |
*Without compression