V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Fenwick Tree

Binary Indexed Tree for logarithmic updates and prefix queries

Balance updates with queries

A plain array updates quickly but needs a linear prefix scan. A prefix-sum array answers quickly but needs a linear rebuild after an update. A Fenwick Tree makes both operations O(log n) by storing carefully chosen partial sums.

Lowbit defines every covered range

lowbit(i) = i & -i isolates the least significant set bit. Entry tree[i] stores a range of that length ending at i. A prefix query jumps backward with i -= lowbit(i); a point update jumps forward with i += lowbit(i) to notify every range that contains the changed position.

3
5
5
11
4
6
3
21

Each bar is tree[1..8]. Prefix queries jump backward with i -= lowbit(i), while point updates jump forward with i += lowbit(i).

1class BIT {
2 tree: number[]; // tree[i] stores a lowbit(i)-wide range sum
3 constructor(n: number) { this.tree = new Array(n + 1).fill(0); }
4 lowbit(i: number) { return i & -i; } // least significant set bit
5 query(i: number): number { // prefix sum a[1..i]
6 let s = 0;
7 for (; i > 0; i -= this.lowbit(i)) // follow the chain backward
8 s += this.tree[i];
9 return s;
10 }
11 update(i: number, d: number) { // a[i] += d
12 for (; i < this.tree.length; i += this.lowbit(i))
13 this.tree[i] += d; // update every covering node
14 }
15}
Source array a[3, 2, 5, 1, 4, 2, 3, 1]
Ruletree[i] covers lowbit(i) values
1 / 9

When to use it

Fenwick Trees are excellent for cumulative frequencies, inversion counting, dynamic ranks, and range sums via query(r) - query(l-1). A segment tree supports more general range operations, but a Fenwick Tree is smaller and often much simpler.

The visualization queries the prefix ending at 6, adds 2 at position 3, then repeats the same query. Compare the two identical lowbit chains to see exactly where the update becomes visible.