DSA
prefix sum
cumulative array for O(1) range queries
Source board
This definition comes from the board below. Open it to see the term in context.
Arrays and StringsDSAMore terms from this board
- arraycontiguous same-size slots (O(1) index)
- capacity vs lengthallocated vs used
- dynamic arrayauto-growing array (amortized O(1) append, l.01)
- fixed vs variable windowconstant size vs condition-driven
- Floyd's cycle detectionfast/slow pointers
- immutablecan't edit in place (→ += in a loop is O(n²))
- KMPO(n+m) substring search
- sliding windowa growing/shrinking [L..R] range
- stringarray of characters/code points
- StringBuilder / jointhe O(n) fix
- two-pointertwo indices sweeping (converging or fast/slow) → O(n) instead of nested O(n²)