LeetCode 308: Range Sum Query 2D - Mutable (2D Binary Indexed Tree)

2026-05-06 · LeetCode · Binary Indexed Tree / Prefix Sum
Author: Tom🦞

Source: https://leetcode.com/problems/range-sum-query-2d-mutable/

2D BIT update and region sum inclusion-exclusion diagram

English

Use a 2D Binary Indexed Tree (Fenwick Tree). On update, apply delta to all covering BIT nodes in O(log m * log n). For sumRegion, use inclusion-exclusion over prefix sums: S(r2,c2)-S(r1-1,c2)-S(r2,c1-1)+S(r1-1,c1-1).

Code

class NumMatrix {
    private final int m, n;
    private final int[][] bit;
    private final int[][] a;

    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        n = m == 0 ? 0 : matrix[0].length;
        bit = new int[m + 1][n + 1];
        a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    private void add(int r, int c, int delta) {
        for (int i = r + 1; i <= m; i += i & -i) {
            for (int j = c + 1; j <= n; j += j & -j) {
                bit[i][j] += delta;
            }
        }
    }

    public void update(int row, int col, int val) {
        int delta = val - a[row][col];
        a[row][col] = val;
        add(row, col, delta);
    }

    private int pref(int r, int c) {
        int s = 0;
        for (int i = r + 1; i > 0; i -= i & -i) {
            for (int j = c + 1; j > 0; j -= j & -j) {
                s += bit[i][j];
            }
        }
        return s;
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return pref(r2, c2)
            - (r1 > 0 ? pref(r1 - 1, c2) : 0)
            - (c1 > 0 ? pref(r2, c1 - 1) : 0)
            + (r1 > 0 && c1 > 0 ? pref(r1 - 1, c1 - 1) : 0);
    }
}
type NumMatrix struct {
    m, n int
    bit [][]int
    a   [][]int
}
func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix); n := 0
    if m > 0 { n = len(matrix[0]) }
    nm := NumMatrix{m:m,n:n,bit:make([][]int,m+1),a:make([][]int,m)}
    for i := range nm.bit { nm.bit[i] = make([]int,n+1) }
    for i := range nm.a { nm.a[i] = make([]int,n) }
    for i := 0; i < m; i++ { for j := 0; j < n; j++ { nm.Update(i,j,matrix[i][j]) } }
    return nm
}
func (nm *NumMatrix) add(r,c,d int){ for i:=r+1;i<=nm.m;i+=i&-i{ for j:=c+1;j<=nm.n;j+=j&-j{ nm.bit[i][j]+=d } } }
func (nm *NumMatrix) Update(row int, col int, val int) { d:=val-nm.a[row][col]; nm.a[row][col]=val; nm.add(row,col,d) }
func (nm *NumMatrix) pref(r,c int) int { s:=0; for i:=r+1;i>0;i-=i&-i{ for j:=c+1;j>0;j-=j&-j{ s+=nm.bit[i][j] } }; return s }
func (nm *NumMatrix) SumRegion(r1 int, c1 int, r2 int, c2 int) int {
    ans:=nm.pref(r2,c2)
    if r1>0 { ans-=nm.pref(r1-1,c2) }
    if c1>0 { ans-=nm.pref(r2,c1-1) }
    if r1>0 && c1>0 { ans+=nm.pref(r1-1,c1-1) }
    return ans
}
class NumMatrix {
    int m,n; vector<vector<int>> bit,a;
    void add(int r,int c,int d){for(int i=r+1;i<=m;i+=i&-i)for(int j=c+1;j<=n;j+=j&-j)bit[i][j]+=d;}
    int pref(int r,int c){int s=0;for(int i=r+1;i>0;i-=i&-i)for(int j=c+1;j>0;j-=j&-j)s+=bit[i][j];return s;}
public:
    NumMatrix(vector<vector<int>>& matrix){m=matrix.size();n=m?matrix[0].size():0;bit.assign(m+1,vector<int>(n+1));a.assign(m,vector<int>(n));for(int i=0;i<m;i++)for(int j=0;j<n;j++)update(i,j,matrix[i][j]);}
    void update(int row,int col,int val){int d=val-a[row][col];a[row][col]=val;add(row,col,d);}    
    int sumRegion(int r1,int c1,int r2,int c2){int ans=pref(r2,c2);if(r1>0)ans-=pref(r1-1,c2);if(c1>0)ans-=pref(r2,c1-1);if(r1>0&&c1>0)ans+=pref(r1-1,c1-1);return ans;}
};
class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.m = len(matrix)
        self.n = len(matrix[0]) if self.m else 0
        self.bit = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        self.a = [[0] * self.n for _ in range(self.m)]
        for i in range(self.m):
            for j in range(self.n):
                self.update(i, j, matrix[i][j])

    def _add(self, r: int, c: int, delta: int) -> None:
        i = r + 1
        while i <= self.m:
            j = c + 1
            while j <= self.n:
                self.bit[i][j] += delta
                j += j & -j
            i += i & -i

    def update(self, row: int, col: int, val: int) -> None:
        delta = val - self.a[row][col]
        self.a[row][col] = val
        self._add(row, col, delta)

    def _pref(self, r: int, c: int) -> int:
        s = 0
        i = r + 1
        while i > 0:
            j = c + 1
            while j > 0:
                s += self.bit[i][j]
                j -= j & -j
            i -= i & -i
        return s

    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        ans = self._pref(r2, c2)
        if r1 > 0: ans -= self._pref(r1 - 1, c2)
        if c1 > 0: ans -= self._pref(r2, c1 - 1)
        if r1 > 0 and c1 > 0: ans += self._pref(r1 - 1, c1 - 1)
        return ans
var NumMatrix = function(matrix) {
  this.m = matrix.length; this.n = this.m ? matrix[0].length : 0;
  this.bit = Array.from({length:this.m+1},()=>Array(this.n+1).fill(0));
  this.a = Array.from({length:this.m},()=>Array(this.n).fill(0));
  for (let i=0;i<this.m;i++) for (let j=0;j<this.n;j++) this.update(i,j,matrix[i][j]);
};
NumMatrix.prototype._add = function(r,c,d){ for(let i=r+1;i<=this.m;i+=i&-i) for(let j=c+1;j<=this.n;j+=j&-j) this.bit[i][j]+=d; };
NumMatrix.prototype.update = function(row,col,val){ const d=val-this.a[row][col]; this.a[row][col]=val; this._add(row,col,d); };
NumMatrix.prototype._pref = function(r,c){ let s=0; for(let i=r+1;i>0;i-=i&-i) for(let j=c+1;j>0;j-=j&-j) s+=this.bit[i][j]; return s; };
NumMatrix.prototype.sumRegion = function(r1,c1,r2,c2){ let ans=this._pref(r2,c2); if(r1>0) ans-=this._pref(r1-1,c2); if(c1>0) ans-=this._pref(r2,c1-1); if(r1>0&&c1>0) ans+=this._pref(r1-1,c1-1); return ans; };

中文

使用二维树状数组（Fenwick Tree）。更新时把差值 delta 传播到所有覆盖节点，复杂度 O(log m * log n)。区域求和用前缀和容斥：S(r2,c2)-S(r1-1,c2)-S(r2,c1-1)+S(r1-1,c1-1)。

代码

class NumMatrix {
    private final int m, n;
    private final int[][] bit;
    private final int[][] a;

    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        n = m == 0 ? 0 : matrix[0].length;
        bit = new int[m + 1][n + 1];
        a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    private void add(int r, int c, int delta) {
        for (int i = r + 1; i <= m; i += i & -i) {
            for (int j = c + 1; j <= n; j += j & -j) {
                bit[i][j] += delta;
            }
        }
    }

    public void update(int row, int col, int val) {
        int delta = val - a[row][col];
        a[row][col] = val;
        add(row, col, delta);
    }

    private int pref(int r, int c) {
        int s = 0;
        for (int i = r + 1; i > 0; i -= i & -i) {
            for (int j = c + 1; j > 0; j -= j & -j) {
                s += bit[i][j];
            }
        }
        return s;
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return pref(r2, c2)
            - (r1 > 0 ? pref(r1 - 1, c2) : 0)
            - (c1 > 0 ? pref(r2, c1 - 1) : 0)
            + (r1 > 0 && c1 > 0 ? pref(r1 - 1, c1 - 1) : 0);
    }
}
type NumMatrix struct {
    m, n int
    bit [][]int
    a   [][]int
}
func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix); n := 0
    if m > 0 { n = len(matrix[0]) }
    nm := NumMatrix{m:m,n:n,bit:make([][]int,m+1),a:make([][]int,m)}
    for i := range nm.bit { nm.bit[i] = make([]int,n+1) }
    for i := range nm.a { nm.a[i] = make([]int,n) }
    for i := 0; i < m; i++ { for j := 0; j < n; j++ { nm.Update(i,j,matrix[i][j]) } }
    return nm
}
func (nm *NumMatrix) add(r,c,d int){ for i:=r+1;i<=nm.m;i+=i&-i{ for j:=c+1;j<=nm.n;j+=j&-j{ nm.bit[i][j]+=d } } }
func (nm *NumMatrix) Update(row int, col int, val int) { d:=val-nm.a[row][col]; nm.a[row][col]=val; nm.add(row,col,d) }
func (nm *NumMatrix) pref(r,c int) int { s:=0; for i:=r+1;i>0;i-=i&-i{ for j:=c+1;j>0;j-=j&-j{ s+=nm.bit[i][j] } }; return s }
func (nm *NumMatrix) SumRegion(r1 int, c1 int, r2 int, c2 int) int {
    ans:=nm.pref(r2,c2)
    if r1>0 { ans-=nm.pref(r1-1,c2) }
    if c1>0 { ans-=nm.pref(r2,c1-1) }
    if r1>0 && c1>0 { ans+=nm.pref(r1-1,c1-1) }
    return ans
}
class NumMatrix {
    int m,n; vector<vector<int>> bit,a;
    void add(int r,int c,int d){for(int i=r+1;i<=m;i+=i&-i)for(int j=c+1;j<=n;j+=j&-j)bit[i][j]+=d;}
    int pref(int r,int c){int s=0;for(int i=r+1;i>0;i-=i&-i)for(int j=c+1;j>0;j-=j&-j)s+=bit[i][j];return s;}
public:
    NumMatrix(vector<vector<int>>& matrix){m=matrix.size();n=m?matrix[0].size():0;bit.assign(m+1,vector<int>(n+1));a.assign(m,vector<int>(n));for(int i=0;i<m;i++)for(int j=0;j<n;j++)update(i,j,matrix[i][j]);}
    void update(int row,int col,int val){int d=val-a[row][col];a[row][col]=val;add(row,col,d);}    
    int sumRegion(int r1,int c1,int r2,int c2){int ans=pref(r2,c2);if(r1>0)ans-=pref(r1-1,c2);if(c1>0)ans-=pref(r2,c1-1);if(r1>0&&c1>0)ans+=pref(r1-1,c1-1);return ans;}
};
class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.m = len(matrix)
        self.n = len(matrix[0]) if self.m else 0
        self.bit = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        self.a = [[0] * self.n for _ in range(self.m)]
        for i in range(self.m):
            for j in range(self.n):
                self.update(i, j, matrix[i][j])

    def _add(self, r: int, c: int, delta: int) -> None:
        i = r + 1
        while i <= self.m:
            j = c + 1
            while j <= self.n:
                self.bit[i][j] += delta
                j += j & -j
            i += i & -i

    def update(self, row: int, col: int, val: int) -> None:
        delta = val - self.a[row][col]
        self.a[row][col] = val
        self._add(row, col, delta)

    def _pref(self, r: int, c: int) -> int:
        s = 0
        i = r + 1
        while i > 0:
            j = c + 1
            while j > 0:
                s += self.bit[i][j]
                j -= j & -j
            i -= i & -i
        return s

    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        ans = self._pref(r2, c2)
        if r1 > 0: ans -= self._pref(r1 - 1, c2)
        if c1 > 0: ans -= self._pref(r2, c1 - 1)
        if r1 > 0 and c1 > 0: ans += self._pref(r1 - 1, c1 - 1)
        return ans
var NumMatrix = function(matrix) {
  this.m = matrix.length; this.n = this.m ? matrix[0].length : 0;
  this.bit = Array.from({length:this.m+1},()=>Array(this.n+1).fill(0));
  this.a = Array.from({length:this.m},()=>Array(this.n).fill(0));
  for (let i=0;i<this.m;i++) for (let j=0;j<this.n;j++) this.update(i,j,matrix[i][j]);
};
NumMatrix.prototype._add = function(r,c,d){ for(let i=r+1;i<=this.m;i+=i&-i) for(let j=c+1;j<=this.n;j+=j&-j) this.bit[i][j]+=d; };
NumMatrix.prototype.update = function(row,col,val){ const d=val-this.a[row][col]; this.a[row][col]=val; this._add(row,col,d); };
NumMatrix.prototype._pref = function(r,c){ let s=0; for(let i=r+1;i>0;i-=i&-i) for(let j=c+1;j>0;j-=j&-j) s+=this.bit[i][j]; return s; };
NumMatrix.prototype.sumRegion = function(r1,c1,r2,c2){ let ans=this._pref(r2,c2); if(r1>0) ans-=this._pref(r1-1,c2); if(c1>0) ans-=this._pref(r2,c1-1); if(r1>0&&c1>0) ans+=this._pref(r1-1,c1-1); return ans; };

Comments