Method
prefix sums
Articles
SRT
Algorithm
Counting sort and radix sort
Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n.
O(n + k) and O(d·(n + b))
2 problems
DS
Data structure
Fenwick tree
Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index.
O(log n) per prefix sum and per update
2 problems
DP
Technique
Interval DP
The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing.
O(n³)
2 problems
Problems
Often together
classic 3 array 2 bit tricks 2 contests 2 sorting 1 stable 1 trie 1 version control 1 interviews 1 in production 1 range queries 1 frequencies 1