lc304-Range Sum Query 2D - Immutable

發表於   |   分類於   |   0 comments   |  

DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    vector<vector<int>> sum;
    int m;
    int n;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        m = matrix.size();
        if (m) {
            n = matrix[0].size();
            for (int i = 0; i<m; i++)
                sum.push_back(vector<int>(n, 0));
        }
        for (int i = 0; i<m; i++) {
            for (int j = 0; j<n; j++) {
                sum[i][j] = ((j>0)?sum[i][j-1]:0) + ((i>0)?sum[i-1][j]:0) - ((i>0&&j>0)?sum[i-1][j-1]:0) + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2][col2]-((row1>0)?sum[row1-1][col2]:0)-((col1>0)?sum[row2][col1-1]:0)+((row1>0&&col1>0)?sum[row1-1][col1-1]:0);
    }
};

没人会想用二维segtree写吧我全当练手了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct row_node{
    row_node * left = nullptr;
    row_node * right = nullptr;
    int down, up;
    int val = 0;
    row_node(int l, int u):up(u),down(l) {}
};
struct col_node {
    col_node * left = nullptr;
    col_node * right = nullptr;
    int down, up;
    row_node * root = nullptr;// row segtree
    col_node(int l, int u):up(u),down(l) {}
};
class NumMatrix {
    int col_num = 0;
    int row_num = 0;
    col_node* root;
    vector<vector<int>> &mat;
public:
    col_node* buildBigTree(int rl, int ru, int cl, int cu) {
        col_node* r = new col_node(rl, ru);
        if (rl == ru) {
            r->root = buildSmallTree(cl, cu, mat[ru]);
            return r;
        }
        if ((rl+ru)/2 >= rl)
            r->left = buildBigTree(rl, (rl+ru)/2, cl, cu);
        if ((rl+ru)/2+1 <= ru)
            r->right = buildBigTree((rl+ru)/2+1, ru, cl, cu);
        if (r->left && r->right)
            r -> root = sumTrees(r->left->root, r->right->root);
        return r;
    }
    
    row_node* sumTrees(row_node* l, row_node*r) {
        row_node* node = new row_node(l->down, l->up);
        node->val = l->val + r->val;
        if (l->left)
            node->left = sumTrees(l->left, r->left);
        if (l->right)
            node->right = sumTrees(l->right, r->right);
        return node;
    }
    
    row_node* buildSmallTree(int l, int u, vector<int> &row) {
        row_node* r = new row_node(l, u);
        if (l == u) {
            r->val = row[l];
            return r;
        }
        if ((l+u)/2 >= l)
            r->left = buildSmallTree(l, (l+u)/2, row);
        if ((l+u)/2+1 <= u)
            r->right = buildSmallTree((l+u)/2+1, u, row);
        r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        return r;
    }
    
    int sumRangeFromBigTree(col_node* r, int l, int u, int r1, int c1, int r2, int c2) {
        if (l == r1 && u == r2)
            return sumRangeFromSmallTree(r->root, 0, col_num-1, c1, c2);
        else {
            int m = (l+u)/2;
            int s1 = (r1<=m)?sumRangeFromBigTree(r->left, l, m, r1, c1, min(r2,m), c2):0;
            int s2 = (r2>m)?sumRangeFromBigTree(r->right, m+1, u, max(r1,m+1), c1, r2, c2):0;
            return s1+s2;
        }
    }
    
    int sumRangeFromSmallTree(row_node* r, int l, int u, int i, int j) {
        if (l == i && u == j)
            return r->val;
        else {
            int m = (l+u)/2;
            int s1 = (i<=m)?sumRangeFromSmallTree(r->left, l, m, i, min(j,m)):0;
            int s2 = (j>m)?sumRangeFromSmallTree(r->right, m+1, u, max(i,m+1), j):0;
            return s1+s2;
        }
    }
    
    NumMatrix(vector<vector<int>> &matrix):mat(matrix) {
        this->row_num = matrix.size();
        if (this->row_num) {
            this->col_num = matrix[0].size();
            if (this->col_num)
                this->root = buildBigTree(0, row_num-1, 0, col_num-1);
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRangeFromBigTree(this->root, 0, row_num-1, row1, col1, row2, col2);
    }
};
// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);