Can be solved using binary indexed treebinary_indexed_tree or Fenwick tree
Real life problems:
- get sum of array quickly
- Counting sort is an integer sorting algorithm that uses the prefix sum of a histogram of key frequencies to calculate the position of each key in the sorted output array
- An early application of parallel prefix sum algorithms was in the design of binary adders, Boolean circuits that can add two n-bit binary numbers. In this application, the sequence of carry bits of the addition can be represented as a scan operation on the sequence of pairs of input bits, using the majority function to combine the previous carry with these two bits. Each bit of the output number can then be found as the exclusive or of two input bits with the corresponding carry bit. By using a circuit that performs the operations of the parallel prefix sum algorithm, it is possible to design an adder that uses O(n) logic gates and O(log n) time steps
Meaning
In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers _x_0, _x_1, _x_2, … is a second sequence of numbers _y_0, _y_1, _y_2, …, the sums of prefixes (running totals) of the input sequence:
_y_0 = _x_0
_y_1 = _x_0 + _x_1
_y_2 = _x_0 + _x_1+ _x_2