Range Sum Query 2D - Mutable ใน C++

สมมติว่าเรามีเมทริกซ์ 2 มิติชื่อ matrix เราต้องคำนวณผลรวมขององค์ประกอบภายในสี่เหลี่ยมผืนผ้าที่กำหนดโดยมุมซ้ายบนและมุมขวาล่าง

เช่น ถ้าอินพุตเป็นเมทริกซ์ 5x5 ตามตาราง (มีการไฮไลท์สีเขียวสำหรับพื้นที่ query) จะมีเมธอดหาผลรวมและอัพเดทค่า หากเราเรียก:

sumRegion(2, 1, 4, 3)
update(3, 2, 2)
sumRegion(2, 1, 4, 3)

ผลลัพธ์จะเป็น 8 และ 10 ตามลำดับ เนื่องจากสี่เหลี่ยมที่กำหนดโดย (2,1) และ (4,3) มีผลรวม = 8

ในการแก้ปัญหานี้ เราจะใช้ 2D Binary Indexed Tree (Fenwick Tree) ทำตามขั้นตอน:

• กำหนดอาร์เรย์ tree และ value 2 มิติ
• Initializer รับ matrix: n,m ขนาด; value = n x m; tree = (n+1) x (m+1); เรียก update(i,j,matrix[i][j]) ทุกเซลล์
• update(row,col,val): delta = val - value[row][col]; value[row][col]=val; ลูป i=row+1..n step i+=i&-i, j=col+1..m step j+=j&-j: tree[i][j] += delta
• sum(row,col): ret=0; ลูป i=row..1 step i-=i&-i, j=col..1 step j-=j&-j: ret += tree[i][j]; คืนค่า ret
• sumRegion(row1,col1,row2,col2): เพิ่มดัชนีทุกตัว 1; คืนค่า sum(r2,c2)+sum(r1-1,c1-1)-sum(r1-1,c2)-sum(r2,c1-1)

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
    int n, m;
    vector> tree, value;
    NumMatrix(vector>& matrix) {
        n = matrix.size(); m = !n ? 0 : matrix[0].size();
        value = vector>(n, vector(m));
        tree = vector>(n+1, vector(m+1));
        for(int i=0;i0;i-=i&-i) for(int j=col;j>0;j-=j&-j) ret += tree[i][j];
        return ret;
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        if(m==0||n==0) return 0;
        row2++; row1++; col1++; col2++;
        return sum(row2,col2) + sum(row1-1,col1-1) - sum(row1-1,col2) - sum(row2,col1-1);
    }
};
main() {
    vector> v = {{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}};
    NumMatrix ob(v);
    cout << ob.sumRegion(2,1,4,3) << endl;
    ob.update(3,2,2);
    cout << ob.sumRegion(2,1,4,3) << endl;
}

อินพุต

matrix 5x5, sumRegion(2,1,4,3), update(3,2,2), sumRegion(2,1,4,3)

เอาต์พุต

8 10