Skip to main content

Fenwick Tree (Range Query)

Learn Fenwick Tree (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Fenwick Tree (Binary Indexed Tree) A Fenwick tree keeps prefix sums while allowing point updates , using one array and a bit trick. Cell i stores the sum of the last lowbit(i) elements ending at i, where lowbit(i) = i & -i . To get a prefix sum, add cell i and then remove its lowest set bit until zero; to update, add the delta and then add the lowest set bit until past n. Both take O(log n) , with far less code than a segment tree.

More lessons in Range Query Techniques