Mode
Array a[]
Prefix prefix[] (length n+1, prefix[0] = 0)
Formula
Pick l and r and press Query
to see prefix[r+1] - prefix[l].
Two duals: read-fast (prefix) vs write-fast (difference)
| Op | Prefix | Diff |
|---|---|---|
| Build | O(n) | O(n) |
| Range query | O(1) | O(n) |
| Range update | O(n) | O(1) |
| Point query | O(1) | O(n)* |
| Space | O(n) | O(n) |