# Translate the question into n * 1d array, i.e. n * segment trees

• I directly used the solution of 307. Range Sum Query - Mutable, basically create an array of segment trees, each row of the matrix is a segment tree, any operations on the matrix would be interpreted and operate on the segment tree arrays

just the performance ain't very good,

``````class NumArray {
public:
NumArray(vector<int> nums) {
m_nums = nums;
n = m_nums.size();
BuildSegmentTree();
}

void update(int i, int val) {
i += n;
m_segmentTree[i] = val;
while (i > 0)
{
int left = i, right = i;
if (i % 2 == 0)
{
right += 1;
}
else
left -= 1;
m_segmentTree[i / 2] = m_segmentTree[left] + m_segmentTree[right];
i /= 2;
}
}

int sumRange(int i, int j) {
i += n;
j += n;
int sum = 0;
while (i <= j)
{
if (i % 2 == 1)
{
sum += m_segmentTree[i];
++i;
}
if (j % 2 == 0)
{
sum += m_segmentTree[j];
--j;
}
i /= 2;
j /= 2;
}
return sum;
}

private:
vector<int> m_nums;
vector<int> m_segmentTree;
int n = 0;

void BuildSegmentTree()
{
m_segmentTree = vector<int>(n * 2);
for (int i = n; i < 2 * n; ++i)
m_segmentTree[i] = m_nums[i - n];
for (int i = n - 1; i > 0; --i)
m_segmentTree[i] = m_segmentTree[2 * i] + m_segmentTree[2 * i + 1];
}
};

class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
m_matrix = matrix;
for (auto row : matrix)
{
m_numArrays.emplace_back(NumArray(row));
}
}

void update(int row, int col, int val) {
m_numArrays[row].update(col, val);
m_matrix[row][col] = val;
}

int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; ++i)
{
sum += m_numArrays[i].sumRange(col1, col2);
}
return sum;
}

private:
vector<NumArray> m_numArrays;
vector<vector<int>> m_matrix;
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.