algorithm - 计算子矩形总和的算法也允许更新

Question

我有一个矩阵 MAT[M][N] 并且有 q 个查询。

In each query I have one of these 2 types of operations 
1. Update MAT[x][y] with k where x,y and k will be given
2. return sum of sub rectangle where left top corner indices are (x1,y1) and right bottom indices are (x2,y2).

前-

Mat - 
1 1 1 1
1 1 1 1
1 1 1 1
queries 
type 1,2,2,5
type 2,1,1,3,3 => 13(output)  

Answer 1

此问题的标准解决方案是二维 binary index tree .它可以在每次查询的 O(log n * log m) 时间内执行所需的操作，并且占用 O(n * m) 额外的空间(其中 n 和 m 是给定矩阵的维度)。它是高效的并且相对容易实现。这是我的代码:

/**
 * Instances of this class represent a two-dimensional binary index tree.
 * 
 * They support the following operations:
 * 1. Updating the value of one element.
 * 2. Finding the sum of all elements in a specified rectangle.
 * 
 * The time complexity of both operation is O(log n * log m), where n and m
 * are the initial matrix dimensions.
 */
template<class T>
class Bit2D {    
public:
    /**
     * Creates a new instance of this class using the matrix as the initial
     * matrix.
     * The matrix must be non-empty.
     */
    Bit2D(const std::vector<std::vector<T>>& matrix): _matrix(matrix) {
        _rowsCount = matrix.size();
        _colsCount = matrix[0].size();
        _sum.assign(_rowsCount, std::vector<T>(_colsCount, 0));
        for (int row = 0; row < _rowsCount; row++) {
            for (int col = 0; col < _colsCount; col++) {
                _update(row, col, _matrix[row][col]);
            }
        }
    }

    /**
     * Returns the sum of all elements in the 
     * ((lowerRow, lowerCol), (upperRow, upperCol)) rectangle.
     * All bounds are inclusive. 
     * lowerRow must be not greater than upperRow.
     * lowerCol must be not greater than upperCol.
     * 
     * If any of these four values is outside the bounds of the initial matrix,
     * undefined behavior is invoked.
     */
    T getSum(int lowerRow, int lowerCol, int upperRow, int upperCol) const {
        return _getSum(upperRow, upperCol) - _getSum(upperRow, lowerCol - 1) 
            - _getSum(lowerRow - 1, upperCol) 
            + _getSum(lowerRow - 1, lowerCol - 1);
    }

    /**
     * Sets the value of the (row, col) element to newValue.
     * 
     * If row or col is outside the bounds of the initial matrix, undefined
     * behavior is invoked.
     */
    void update(int row, int col, T newValue) {
        _update(row, col, newValue - _matrix[row][col]);
        _matrix[row][col] = newValue;
    }

private:   
    std::vector<std::vector<T>> _matrix;
    std::vector<std::vector<T>> _sum;
    int _rowsCount;
    int _colsCount;

    int _getPrevious(int index) const {
        return (index & (index + 1)) - 1;
    }

    int _getNext(int index) const {
        return index | (index + 1);
    }

    T _getSum(int upperRow, int upperCol) const {
        T res = 0;
        for (int row = upperRow; row >= 0; row = _getPrevious(row)) {
            for (int col = upperCol; col >= 0; col = _getPrevious(col)) {
                res += _sum[row][col];
            }
        }
        return res;
    }

    void _update(int row, int col, T delta) {
        for (int curRow = row; curRow < _rowsCount; curRow = _getNext(curRow)) {
            for (int curCol = col; curCol < _colsCount; curCol = _getNext(curCol)) {
                _sum[curRow][curCol] += delta;
            }
        }
    }
};