Range Sum Query 2D - Mutable

This page explains Java solution to problem Range Sum Query 2D - Mutable using Binary Indexed Tree algorithm.

Problem Statement

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Input:
matrix = [
       [3, 0, 1, 4, 2],
       [5, 6, 3, 2, 1],
       [1, 2, 0, 1, 5],
       [4, 1, 0, 1, 7],
       [1, 0, 3, 0, 5]
]
Output:
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Solution

package com.vc.hard;

class RangeSumQuery2dMutable {
    int m;
    int n;
    int[][] tree;
    int[][] matrix;

    public RangeSumQuery2dMutable(int[][] matrix) {
        this.m = matrix.length;
        if(m == 0) return;
        this.n = matrix[0].length;
        this.matrix = matrix;
        tree = new int[m + 1][n + 1];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                set(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if(m == 0 || n == 0) return;
        int delta = val - matrix[row][col];
        matrix[row][col] = val;
        set(row, col, delta);
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum(row2 + 1, col2 + 1) + sum(row1, col1) - sum(row1, col2 + 1) - sum(row2 + 1, col1);
    }

    private void set(int row, int col, int val) {
        if(m == 0 || n == 0) return;
        for(int i = row + 1; i <= m; i = getNext(i)) {
            for(int j = col + 1; j <= n; j = getNext(j)) {
                tree[i][j] += val;
            }
        }
    }

    private int sum(int row, int col) {
        int sum = 0;
        if(m == 0 || n == 0) return sum;
        for(int i = row; i > 0; i = getParent(i)) {
            for(int j = col; j > 0; j = getParent(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }

    private int getParent(int x) {
        return x - (x & -x);
    }

    private int getNext(int x) {
        return x + (x & -x);
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */

Time Complexity

O(M * N * log(M * N)) to Generate Binary Indexed Tree using Array
O(log (M * N)) to Update element in an input array & Binary Indexed Tree
O(log (M * N)) to Sum elements in an input range Where
M is total number rows in an input array
N is total number cols in an input array

Space Complexity

O(M * N) Where
M is total number rows in an input array
N is total number cols in an input array