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


  • 0
    D

    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;
    };
    
    

Log in to reply
 

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