golang 解法, 执行用时: 16 ms, 内存消耗: 6.9 MB, 提交时间: 2023-10-22 08:22:24
type NumMatrix struct {
s [][]int
m [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m := make([][]int, len(matrix))
for i := range m{
m[i] = make([]int, len(matrix[0])+1)
}
for i := range matrix{
for j := range matrix[i]{
m[i][j+1] += m[i][j] + matrix[i][j]
}
}
return NumMatrix{s:matrix, m:m}
}
func (this *NumMatrix) Update(row int, col int, val int) {
// 更新第row行的前缀和
diff := val-this.s[row][col]
this.s[row][col] = val
for col+1<len(this.m[row]){
this.m[row][col+1] += diff
col++
}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
var ans int
for row1<=row2{
ans += this.m[row1][col2+1] - this.m[row1][col1]
row1++
}
return ans
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/
golang 解法, 执行用时: 24 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-22 08:22:07
type NumMatrix struct {
matrix [][]int
preArr [][]int
}
func Constructor(matrix [][]int) NumMatrix {
preArr := make([][]int, len(matrix))
for i := 0; i < len(preArr); i++ {
preArr[i] = make([]int, len(matrix[i]))
preArr[i][0] = matrix[i][0]
if i != 0 {
preArr[i][0] += preArr[i-1][0]
}
}
for j := 0; j < len(preArr[0]); j++ {
preArr[0][j] = matrix[0][j]
if j != 0 {
preArr[0][j] += preArr[0][j-1]
}
}
for i := 1; i < len(preArr); i++ {
for j := 1; j < len(preArr[i]); j++ {
preArr[i][j] = matrix[i][j] + preArr[i-1][j] + preArr[i][j-1] - preArr[i-1][j-1]
}
}
return NumMatrix{matrix: matrix, preArr: preArr}
}
func (this *NumMatrix) Update(row int, col int, val int) {
now := this.matrix[row][col]
this.matrix[row][col] = val
for i := row; i < len(this.preArr); i++ {
for j := col; j < len(this.preArr[i]); j++ {
this.preArr[i][j] += val - now
}
}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
res := this.preArr[row2][col2]
if row1 != 0 {
res -= this.preArr[row1-1][col2]
}
if col1 != 0 {
res -= this.preArr[row2][col1-1]
}
if row1 != 0 && col1 != 0 {
res += this.preArr[row1-1][col1-1]
}
return res
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/
golang 解法, 执行用时: 20 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-22 08:21:34
type NumMatrix struct {
m, n int
nums []int
tree []int
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
h := NumMatrix{
m: m,
n: n,
nums: make([]int, m*n),
tree: make([]int, m*n+1),
}
for i := range matrix {
for j := range matrix[0] {
h.update(i*n+j+1, matrix[i][j])
}
}
return h
}
func (this *NumMatrix) Update(row int, col int, val int) {
this.update(row*this.n+col+1, val)
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) (sums int) {
for i := row1; i <= row2; i++ {
sums += this.sumRange(this.n*i+col1+1, this.n*i+col2+1)
}
return
}
func (this *NumMatrix) update(i int, val int) {
diff := val - this.nums[i-1]
this.nums[i-1] = val
for j := i; j < len(this.tree); j += (j & -j) {
this.tree[j] += diff
}
}
func (this *NumMatrix) sumRange(i, j int) int {
return this.sum(j) - this.sum(i-1)
}
func (this *NumMatrix) sum(i int) (x int) {
for j := i; j > 0; j -= (j & -j) {
x += this.tree[j]
}
return
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/
golang 解法, 执行用时: 24 ms, 内存消耗: 10.1 MB, 提交时间: 2023-10-22 08:21:11
type NumMatrix struct {
root *SegTreeNode
matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return NumMatrix{}
}
return NumMatrix{
root: buildTree(matrix, 0, 0, len(matrix) - 1, len(matrix[0]) - 1),
matrix: matrix,
}
}
func (this *NumMatrix) Update(row int, col int, val int) {
if this.root == nil {
return
}
this.root.Update(row, col, val)
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
if this.root == nil {
return 0
}
return this.root.Query(row1, col1, row2, col2)
}
type SegTreeNode struct {
ur, uc, lr, lc, sum int
children [4]*SegTreeNode
}
func buildTree(matrix [][]int, ur, uc, lr, lc int) *SegTreeNode {
if ur > lr || uc > lc {
return nil
}
root := &SegTreeNode{ur: ur, uc: uc, lr: lr, lc: lc, sum: matrix[ur][uc]}
if ur == lr && uc == lc {
return root
}
mr, mc := ur + (lr - ur) / 2, uc + (lc - uc) / 2
root.children[0] = buildTree(matrix, ur, uc, mr, mc)
root.children[1] = buildTree(matrix, ur, mc + 1, mr, lc)
root.children[2] = buildTree(matrix, mr + 1, uc, lr, mc)
root.children[3] = buildTree(matrix, mr + 1, mc + 1, lr, lc)
sum := 0
for i := 0; i < 4; i++ {
if root.children[i] != nil {
sum += root.children[i].sum
}
}
root.sum = sum
return root
}
func (this *SegTreeNode) Update(r, c, val int) {
if this.ur == this.lr && this.uc == this.lc {
this.sum = val
return
}
mr, mc := this.ur + (this.lr - this.ur) / 2, this.uc + (this.lc - this.uc) / 2
if r <= mr && c <= mc {
this.children[0].Update(r, c, val)
} else if r <= mr && c > mc {
this.children[1].Update(r, c, val)
} else if r > mr && c <= mc {
this.children[2].Update(r, c, val)
} else {
this.children[3].Update(r, c, val)
}
sum := 0
for i := 0; i < 4; i++ {
if this.children[i] != nil {
sum += this.children[i].sum
}
}
this.sum = sum
}
func (this *SegTreeNode) Query(ur, uc, lr, lc int) int {
if this.ur == ur && this.uc == uc && this.lr == lr && this.lc == lc {
return this.sum
}
mr, mc := this.ur + (this.lr - this.ur) / 2, this.uc + (this.lc - this.uc) / 2
sum := 0
if ur <= mr && uc <= mc {
sum += this.children[0].Query(ur, uc, min(lr, mr), min(lc, mc))
}
if ur <= mr && lc > mc {
sum += this.children[1].Query(ur, max(uc, mc + 1), min(lr, mr), lc)
}
if lr > mr && uc <= mc {
sum += this.children[2].Query(max(ur, mr + 1), uc, lr, min(lc, mc))
}
if lr > mr && lc > mc {
sum += this.children[3].Query(max(ur, mr + 1), max(uc, mc + 1), lr, lc)
}
return sum
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/
cpp 解法, 执行用时: 20 ms, 内存消耗: 12.8 MB, 提交时间: 2023-10-22 08:20:07
class NumMatrix {
private:
vector<vector<int>> clone;
vector<vector<int>> tree;
int lowbit(int x) {
return x & (-x);
}
int getSum(int row, int col) {
int ans = 0;
for (int i = row; i > 0; i -= lowbit(i))
for (int j = col; j > 0; j -= lowbit(j))
ans += tree[i][j];
return ans;
}
public:
NumMatrix(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return;
int n = matrix.size(), m = matrix[0].size();
clone.assign(n, vector<int> (m));
tree.assign(n + 1, vector<int> (m + 1));
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
update(i, j, matrix[i][j]);
}
void update(int row, int col, int val) {
int delta = val - clone[row][col];
clone[row][col] = val;
for (int i = row + 1; i < tree.size(); i += lowbit(i))
for (int j = col + 1; j < tree[0].size(); j += lowbit(j))
tree[i][j] += delta;
}
int sumRegion(int row1, int col1, int row2, int col2) {
return getSum(row2 + 1, col2 + 1) - getSum(row1, col2 + 1) - getSum(row2 + 1, col1) + getSum(row1, col1);
}
};
/**
* 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);
*/
python3 解法, 执行用时: 408 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-22 08:19:34
class BitTree: #树状数组，动态前缀和
def __init__(self, n: int):
self.tree = [0 for _ in range(n + 1)]
self.n = n
def lowbit(self, x: int) -> int:
return x & (-x)
def update(self, i: int, diff: int) -> None:
i += 1
while i <= self.n:
self.tree[i] += diff
i += self.lowbit(i)
def query(self, i: int) -> int: #i是普通数组中的index
i += 1
presum = 0
while i > 0:
presum += self.tree[i]
i -= self.lowbit(i)
return presum
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
self.Row, self.Col = len(matrix), len(matrix[0])
n = self.Row * self.Col
self.BT = BitTree(n)
for r in range(self.Row):
for c in range(self.Col):
ID = r * self.Col + c
self.BT.update(ID, matrix[r][c])
def update(self, row: int, col: int, val: int) -> None:
ID = row * self.Col + col
diff = val - self.matrix[row][col]
self.matrix[row][col] = val
self.BT.update(ID, diff)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
res = 0
for r in range(row1, row2 + 1):
ID1 = r * self.Col + col1
ID2 = r * self.Col + col2
res += (self.BT.query(ID2) - self.BT.query(ID1 - 1))
return res
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)
python3 解法, 执行用时: 996 ms, 内存消耗: 20.2 MB, 提交时间: 2023-10-22 08:19:21
class SegTree: #线段树--数组实现
def __init__(self, n: int):
self.treesum = [0 for _ in range(4 * n)]
self.n = n
def update(self, idx: int, diff: int) -> None:
self._update(0, 0, self.n - 1, idx, diff)
def query(self, ql: int, qr: int) -> int:
return self._query(0, 0, self.n - 1, ql, qr)
def _update(self, root: int, l: int, r: int, ID: int, diff: int) -> None:
if l == r == ID:
self.treesum[root] += diff
return
left = 2 * root + 1
right = 2 * root + 2
mid = (l + r) // 2
if ID <= mid:
self._update(left, l, mid, ID, diff)
else:
self._update(right, mid + 1, r, ID, diff)
self.treesum[root] = self.treesum[left] + self.treesum[right]
def _query(self, root: int, l: int, r: int, ql: int, qr: int) -> int:
if l == ql and r == qr:
return self.treesum[root]
left = 2 * root + 1
right = 2 * root + 2
mid = (l + r) // 2
if qr <= mid:
return self._query(left, l, mid, ql, qr)
elif mid + 1 <= ql:
return self._query(right, mid + 1, r, ql, qr)
else:
return self._query(left, l, mid, ql, mid) + self._query(right, mid+1, r, mid+1, qr)
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
self.Row, self.Col = len(matrix), len(matrix[0])
n = self.Row * self.Col
self.ST = SegTree(n)
for r in range(self.Row):
for c in range(self.Col):
ID = r * self.Col + c
self.ST.update(ID, matrix[r][c])
def update(self, row: int, col: int, val: int) -> None:
ID = row * self.Col + col
diff = val - self.matrix[row][col]
self.matrix[row][col] = val
self.ST.update(ID, diff)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
res = 0
for r in range(row1, row2 + 1):
ID1 = r * self.Col + col1
ID2 = r * self.Col + col2
res += self.ST.query(ID1, ID2)
return res
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)
cpp 解法, 执行用时: 44 ms, 内存消耗: 13.7 MB, 提交时间: 2023-10-22 08:19:01
class SegTree { //线段树--数组实现
public:
vector<int> treesum;
int n;
SegTree() {}
SegTree(int n)
{
this->treesum.resize(4 * n, 0);
this->n = n;
}
void update(int idx, int diff)
{
_update(0, 0, n - 1, idx, diff);
}
int query(int ql, int qr)
{
return _query(0, 0, n - 1, ql, qr);
}
void _update(int root, int l, int r, int ID, int diff)
{
if (l == ID && r == ID)
{
treesum[root] += diff;
return ;
}
int left = 2 * root + 1;
int right = 2 * root + 2;
int mid = (l + r) / 2;
if (ID <= mid)
_update(left, l, mid, ID, diff);
else
_update(right, mid + 1, r, ID, diff);
treesum[root] = treesum[left] + treesum[right];
}
int _query(int root, int l, int r, int ql, int qr)
{
if (l == ql && r == qr)
return treesum[root];
int left = 2 * root + 1;
int right = 2 * root + 2;
int mid = (l + r) / 2;
if (qr <= mid)
return _query(left, l, mid, ql, qr);
else if (mid + 1 <= ql)
return _query(right, mid + 1, r, ql, qr);
else
return _query(left, l, mid, ql, mid) + _query(right, mid + 1, r, mid + 1, qr);
}
};
class NumMatrix {
public:
vector<vector<int>> matrix;
int Row, Col;
SegTree ST;
NumMatrix(vector<vector<int>>& matrix) {
this->matrix = matrix;
this->Row = matrix.size(), this->Col = matrix[0].size();
int n = Row * Col;
this->ST = SegTree(n);
for (int r = 0; r < Row; r ++)
{
for(int c = 0; c < Col; c ++)
{
int ID = r * Col + c;
ST.update(ID, matrix[r][c]);
}
}
}
void update(int row, int col, int val) {
int ID = row * Col + col;
int diff = val - matrix[row][col];
matrix[row][col] = val;
ST.update(ID, diff);
}
int sumRegion(int row1, int col1, int row2, int col2) {
int res = 0;
for (int r = row1; r <= row2; r ++)
{
int ID1 = r * Col + col1;
int ID2 = r * Col + col2;
res += ST.query(ID1, ID2);
}
return res;
}
};
/**
* 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);
*/
cpp 解法, 执行用时: 24 ms, 内存消耗: 12.8 MB, 提交时间: 2023-10-22 08:18:21
class BitTree { //树状数组，动态前缀和
public:
vector<int> tree;
int n;
BitTree(){} //定义一个构造函数。不然solution没法调用
BitTree(int n) {
tree.resize(n + 1, 0);
this->n = n;
}
int lowbit(int x) {
return x & (-x);
}
void update(int i, int diff) {
i ++; //BitTree从1开始，普通数组从0开始计
while(i <= n)
{
tree[i] += diff;
i += lowbit(i);
}
}
int query(int i) {
i ++; //BitTree从1开始，普通数组从0开始计
int presum = 0;
while (i > 0)
{
presum += tree[i];
i -= lowbit(i);
}
return presum;
}
};
class NumMatrix {
public:
vector<vector<int>> matrix;
int Row, Col;
BitTree BT;
NumMatrix(vector<vector<int>>& matrix) {
this->matrix = matrix;
this->Row = matrix.size(), this->Col = matrix[0].size();
int n = Row * Col;
this->BT = BitTree(n);
for (int r = 0; r < Row; r ++)
{
for (int c = 0; c < Col; c ++)
{
int ID = r * Col + c;
BT.update(ID, matrix[r][c]);
}
}
}
void update(int row, int col, int val) {
int ID = row * Col + col;
int diff = val - matrix[row][col];
matrix[row][col] = val;
BT.update(ID, diff);
}
int sumRegion(int row1, int col1, int row2, int col2) {
int res = 0;
for(int r = row1; r <= row2; r++)
{
int ID1 = r * Col + col1;
int ID2 = r * Col + col2;
res += (BT.query(ID2) - BT.query(ID1 - 1));
}
return res;
}
};
/**
* 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);
*/
cpp 解法, 执行用时: 16 ms, 内存消耗: 12.9 MB, 提交时间: 2023-10-22 08:17:15
#define lowbit(x) ((x) & (-x))
class NumMatrix {
public:
int n, m;
vector<vector<int>> M;
vector<vector<int>> matrix;
NumMatrix(vector<vector<int>> &matrix) : matrix(matrix) {
n = matrix.size();
if (n) m = matrix[0].size();
else m = 0;
M = vector<vector<int>>(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
modify(i + 1, j + 1, matrix[i][j]);
}
}
}
void modify(int i, int j, int delta) {
for (int x = i; x <= n; x += lowbit(x)) {
for (int y = j; y <= m; y += lowbit(y)) {
M[x][y] += delta;
}
}
}
int getsum(int i, int j) {
int ret = 0;
for (int x = i; x; x -= lowbit(x)) {
for (int y = j; y; y -= lowbit(y)) {
ret += M[x][y];
}
}
return ret;
}
void update(int x, int y, int v) {
int delta = v - matrix[x][y];
matrix[x][y] = v;
modify(x + 1, y + 1, delta);
}
int sumRegion(int x1, int y1, int x2, int y2) {
return getsum(x2 + 1, y2 + 1) - getsum(x1, y2 + 1) - getsum(x2 + 1, y1) + getsum(x1, y1);
}
};
/**
* 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);
*/
java 解法, 执行用时: 10 ms, 内存消耗: 47.7 MB, 提交时间: 2023-10-22 08:16:56
class NumMatrix {
private int[][] matrix;
private int[][] rowSumArr; // 保存每个元素(i, j)在第i行的前j+1项的和。
private int rowCount;
private int colCount;
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
rowCount = matrix.length;
colCount = matrix[0].length;
rowSumArr = new int[rowCount][colCount];
for (int i = 0; i < rowCount; i++) {
rowSumArr[i][0] = matrix[i][0];
for (int j = 1; j < colCount; j++) {
rowSumArr[i][j] = rowSumArr[i][j-1] + matrix[i][j];
}
}
}
public void update(int row, int col, int val) {
matrix[row][col] = val;
int fromCol = col;
if (col == 0) {
rowSumArr[row][col] = matrix[row][col];
fromCol = col + 1;
}
for (int j = fromCol; j < colCount; j++) {
rowSumArr[row][j] = rowSumArr[row][j-1] + matrix[row][j];
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) {
sum += col1 == 0 ? rowSumArr[i][col2] : rowSumArr[i][col2] - rowSumArr[i][col1-1];
}
return sum;
}
}
/**
* 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);
*/
