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
Prefix SumPrefix | Segment TreeTrees | |
|---|---|---|
| Use case | Many range-sum queries on an array that never changes. | Range queries interleaved with point (or lazy range) updates; any associative operation. |
| Requirements | An invertible operation (sum, XOR); static data. | An associative combine function; 4n array or explicit nodes. |
| Time complexity | O(n) build, O(1) query, O(n) per update. | O(n) build, O(log n) query and update. |
| Space complexity | O(n). | O(n) (about 4n slots in the array form). |
| Strengths | Trivial to write; constant-time queries; combines with a hash map to count subarrays. | Supports min/max/gcd/custom merges and updates; lazy propagation gives range updates. |
| Weaknesses | Any update invalidates every later prefix; only works for invertible operations. | More code and constant factor; overkill for static sums. |
| Example problems | Range sum query immutable, subarray sum equals k, product of array except self. | Range sum query mutable, count of smaller numbers after self, sliding-window range min with updates. |
| Choose this when | Choose prefix sums when the array is static and the query is a sum-like invertible aggregate. | Choose a segment tree (or Fenwick tree for sums) when updates and queries interleave, or the operation is min/max/gcd. |