Overview
A Fenwick tree stores partial sums or other invertible prefix aggregates in a compact array. Updates and prefix queries jump through indices by adding or removing the least significant set bit.
CoreSource checked
Fenwick Tree
Maintains prefix aggregates in an array using index ranges encoded by low bits.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Range Query Structure
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Binary Indexed Tree, BIT
Core Concepts
prefix aggregatebinary indexed rangesleast significant bitpoint updatestored invariantrange aggregateinteger key rangerange query structure
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(log n)
Worst
O(log n)
Space
O(n)
When to Use
- Use when point updates and prefix queries are both needed.
- Use when the operation has an inverse or prefix differences are enough for range queries.
When Not to Use
- Avoid when arbitrary range updates and range queries need richer lazy propagation.
- Avoid when multidimensional or noninvertible operations make a segment tree clearer.
What It Does
- Stores partial aggregates in indexed buckets
- Updates all buckets covering one position
- Computes prefix queries by walking low-bit ranges
Use Cases
- Dynamic prefix sums
- Frequency tables with rank queries
- Inversion counting and order-statistic helpers
Inputs
- Array of values
- Point updates
- Prefix queries
Outputs
- Prefix or range aggregate answers
Key Formulas (1)
Parent step
indexnext = index + (index & −index)
index_next = index + (index & -index)Moves upward through Binary Indexed Tree ranges during an update.
Pseudocode
- 1.For update at one-based index i
- 2.While i <= n, add delta to tree[i] and set i += lowbit(i)
- 3.For prefix query at one-based index i
- 4.Accumulate tree[i] and set i -= lowbit(i) until i is zero
- 5.Return the accumulated prefix value
Canonical Example
- Input
- values [3, 1, 4], update index 1 by +2, query prefix through index 2
- Output
- 10
- Explanation
- The updated values are [3, 3, 4], and the prefix sum is 10 if inclusive through 2; APIs must define inclusivity clearly.
Implementation Notes
- Use one-based internal indexes even if the public API is zero-based.
- Test prefix queries at the first, middle, and last positions.
- Document whether values are sums, counts, or another associative aggregate.
Common Pitfalls
- Mixing zero-based and one-based indexing breaks low-bit jumps.
- Range queries require subtracting two prefixes, which depends on the operation.
- Forgetting to update all covering buckets gives stale sums.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow indexes covering ranges determined by their lowest set bit.
Step 1 of 5: For update at one-based index i
binary-index-rangesNotes
Fenwick tree APIs should state index base and whether query endpoints are inclusive.
Sources (2)
What each reference supports for this entry.
Fenwick Tree
PaperOriginal reference for binary indexed trees and cumulative frequency updates.
Open sourceIntroduction to Algorithms (CLRS)
BookAlgorithms textbook support for Fenwick Tree's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toSegment Tree
Fenwick trees are smaller and simpler for prefix-style aggregates.
Conceptual neighborSparse Table
Both answer aggregate-style queries from precomputed indexed summaries, but with different update tradeoffs.
Related Algorithms
Tags
Data StructureRange QueryInteger Data