Segment Trees and Fenwick Trees
← Back to Tree Structures
Specialized trees for answering range queries (sum, min, max) over an array and supporting point or range updates efficiently.
Key Properties
Complexity
| Structure | Build | Query | Update | Notes |
|---|---|---|---|---|
| Segment Tree | O(n) | O(log n) | O(log n) | More flexible |
| Fenwick Tree (BIT) | O(n) | O(log n) | O(log n) | Less memory, simpler code, less flexible |
Related
- Arrays (underlying data)
- Binary Trees (structure)