Back to algorithmsPodstawowy
Prefix Sums
A preprocessing technique that allows for fast calculation of range sums in an array.
O(n) budowa, O(1) zapytanieO(n)OIJOILOGIA
Applications
- •Fast range sum queries
- •Range problems
- •Optimizing multiple queries
Complexity
Time
O(n) budowa, O(1) zapytanie
Memory
O(n)
How does Prefix Sums work?
A preprocessing technique that allows for fast calculation of range sums in an array.
Analogy
Like an odometer in a car - if you want to know how far you traveled from point A to B, just subtract the odometer value at A from the value at B.