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

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

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

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

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

Repovive

2D Fenwick Tree - Fenwick Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

2D Fenwick Tree

Extending to matrices

2D BIT supports:

Point update at $(x, y)$
Prefix sum query for rectangle $(1, 1)$ to $(x, y)$

The structure nests the 1D operations:

def update2D(x, y, delta):
    i = x
    while i <= n:
        j = y
        while j <= m:
            tree[i][j] += delta
            j += j & (-j)
        i += i & (-i)

def query2D(x, y):
    result = 0
    i = x
    while i > 0:
        j = y
        while j > 0:
            result += tree[i][j]
            j -= j & (-j)
        i -= i & (-i)
    return result

Time: $O(\log n \cdot \log m)$ for both operations. Space: $O(nm)$ .