Concepts4
βMathAdvanced
Divisor Function Sums
Summing the divisor function d(i) up to n equals counting lattice points under the hyperbola xy β€ n, which can be done in O(βn) using floor-division blocks.
#divisor function#euler totient#mobius function+11
βοΈAlgorithmAdvanced
Divide and Conquer DP Optimization
Divide and Conquer DP optimization speeds up DP transitions of the form dp[i][j] = min over k of dp[i-1][k] + C(k, j) when the optimal k is monotone in j.
#divide and conquer dp#monge array#quadrangle inequality+10
βοΈAlgorithmAdvanced
Knuth Optimization
Knuth Optimization speeds up a class of interval dynamic programming (DP) from O(n^3) to O(n^2) by exploiting the monotonicity of optimal split points.
#knuth optimization#interval dp#quadrangle inequality+12
ποΈData StructureAdvanced
Wavelet Tree
A wavelet tree is a recursive data structure built over a sequenceβs alphabet that answers rank, select, and quantile (k-th smallest) queries in O(log Ο) time, where Ο is the number of distinct values.
#wavelet tree#wavelet matrix#rank select+11