Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
Segment TreeTrees | Fenwick TreeTrees | |
|---|---|---|
| Use case | Range queries for any associative operation, with point or lazy range updates. | Prefix sums with point updates; range sums via subtraction. |
| Requirements | Associative combine; roughly 4n storage. | An invertible operation (sum, XOR); 1-indexed array of size n + 1. |
| Time complexity | O(n) build, O(log n) query and update. | O(n log n) (or O(n)) build, O(log n) query and update. |
| Space complexity | O(4n). | O(n). |
| Strengths | Handles min/max/gcd, range assignment, lazy propagation, and "first index where prefix exceeds x" searches. | About ten lines; very fast; tiny memory; easy to extend to 2D. |
| Weaknesses | Longer code, larger constant, more memory. | Only invertible operations; no lazy range updates without a second tree; no arbitrary range min. |
| Example problems | Range sum query mutable, range minimum with updates, counting inversions online. | Range sum query mutable, count of smaller numbers after self, number of inversions. |
| Choose this when | Choose a segment tree when the operation is not invertible (min, max, gcd) or you need lazy range updates. | Choose a Fenwick tree for sums/XOR with point updates; it is shorter, faster and enough for most interview range problems. |