Published by Dimitris Kougioumtzis · Updated
Build the range-query structure and answer an inclusive query. Optionally set one array value before querying.
Use one-based index low bits to store partial sums; queries remove a low bit while updates climb to enclosing ranges.
When to use Fenwick tree range sum
Interleaved point updates and range sums.
Choosing an alternative
Segment trees support broader operations; sparse tables suit static minima.
Worked example: input and state changes
Example input
1,2,3,4,5 | 1,4 | 2,8
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0 ], "active": [] }Step 4: Update Fenwick node 2 by 2.
State at this checkpoint
{ "values": [ 0, 1, 3, 0, 1, 0 ], "active": [ 2 ] }Step 8: Update Fenwick node 4 by 4.
State at this checkpoint
{ "values": [ 0, 1, 3, 3, 10, 0 ], "active": [ 4 ] }Step 11: Update Fenwick node 4 by 5.
State at this checkpoint
{ "values": [ 0, 1, 3, 8, 15, 5 ], "active": [ 4 ] }Step 15: Range sum [1,4] = 19.
State at this checkpoint
{ "values": [ 0, 1, 3, 8, 15, 5 ], "active": [], "result": 19, "input": [ 1, 2, 8, 4, 5 ] }
Expected final state
Range sum [1,4] = 19.
Complexity and input bounds
Family: Trees. Time complexity: O(n log n) build; O(log n) update/query.
Space complexity: O(n) tree storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1–24 values (0–99) | left,right | optional index,newValue; indices are zero-based.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Internal indices are one-based although playground positions are zero-based; a range sum subtracts two prefix sums.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 | // 1–24 values 0–99, inclusive valid left/right indices. updateIndex=-1 skips update; otherwise set a[updateIndex] to newValue (0–99). Returns range sum; mutates a when updating. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, left, right, updateIndex, newValue) { let tree = Array(256).fill(0); for (let i = 0; i < n; i++) { for (let p = i + 1; p <= n; p += p & -p) { tree[p] += a[i]; } } if (updateIndex >= 0) { let delta = newValue - a[updateIndex]; a[updateIndex] = newValue; for (let p = updateIndex + 1; p <= n; p += p & -p) { tree[p] += delta; } } let sum = 0; for (let p = right + 1; p > 0; p -= p & -p) { sum += tree[p]; } for (let p = left; p > 0; p -= p & -p) { sum -= tree[p]; } return sum; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- A new data structure for cumulative frequency tables
Peter M. Fenwick (1994). Research paper.