#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/fenwick-trees/fenwick-tree-structure

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/fenwick-trees/fenwick-tree-structure

Repovive

Fenwick Tree Structure - Fenwick Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Fenwick Tree Structure

What each position stores

A Fenwick Tree uses 1-based indexing. Position $i$ stores the sum of elements from $i - \text{lowbit}(i) + 1$ to $i$ .

Index (binary):  1(1)  2(10)  3(11)  4(100)  5(101)  6(110)  7(111)  8(1000)
Stores sum of:   [1]   [1,2]   [3]   [1-4]    [5]    [5,6]    [7]    [1-8]

Position $1$ stores $1$ element (lowbit = 1). Position $2$ stores $2$ elements (lowbit = 2). Position $4$ stores $4$ elements (lowbit = 4). Position $8$ stores $8$ elements (lowbit = 8).

Each position covers a different "responsibility range." Together, they allow computing any prefix sum in $O(\log n)$ additions.