2D Fenwick Tree

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)$.