Why cannot segment tree be applied to range sum query 2d?


  • 0
    D

    Segment tree can be applied in one dimension case. Update time is O(lgn), and query time is O(lgn). However, I have tried once segment tree 2D version, the online judge reported: time limit exceeded.

    Why cannot segment tree be applied to range sum query 2d?


  • 0
    X

    My code is accepted using segment tree, even though it's very very slow. 421 ms running time.

    class SegmentTreeNode {
    public:
        int start;
        int end;
        int sum;
        SegmentTreeNode *left;
        SegmentTreeNode *right;
        SegmentTreeNode(int start, int end) {
            this->start = start;
            this->end = end;
            this->sum = 0;
            left = right = NULL;
        }
    };
    
    class NumMatrix {
        int row;
        int column;
        vector <SegmentTreeNode*> nodes;
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if (matrix.size() == 0 || matrix[0].size() == 0) return;
            row = matrix.size();
            column = matrix[0].size();
            // build row number of segment trees to store all elements sum
            for (int i = 0; i < row; i++) {
                SegmentTreeNode* tmpRoot = build(0, column - 1);
                for (int j = 0; j < column; j++) {
                    updateSeg(tmpRoot, j, matrix[i][j]);
                }
                nodes.push_back(tmpRoot);
            }
        }
        
        SegmentTreeNode* build(int start, int end) {
            SegmentTreeNode* root = new SegmentTreeNode(start, end);
            if (start < end) {
                int middle = (start + end) >> 1;
                root->left = build(start, middle);
                root->right = build(middle + 1, end);
            }
            return root;
        }
        
        void updateSeg(SegmentTreeNode* root, int index, int value) {
            if (root == NULL || index < root->start || index > root->end) return;
            if (root->start == root->end && root->start == index) {
                root->sum = value;
            } else {
                int middle = (root->start + root->end) / 2;
                index <= middle ? updateSeg(root->left, index, value) : updateSeg(root->right, index, value);
                root->sum = root->left->sum + root->right->sum;
            }
        }
        
        void update(int row, int col, int val) {
            updateSeg(nodes[row], col, val);
        }
        
        int query(SegmentTreeNode* root, int start, int end) {
            if (root == NULL || end < root->start || start > root->end) return 0;
            if (start <= root->start && end >= root->end) return root->sum;
            return query(root->left, start, end) + query(root->right, start, end);
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            if (row1 > row2 || col1 > col2) return 0;
            if (row1 < 0 || row1 > row || row2 < 0 || row2 > row) return 0;
            if (col1 < 0 || col1 > column || col2 < 0 || col2 > column) return 0;
            int resSum = 0;
            for (int i = row1; i <= row2; i++) {
                resSum += query(nodes[i], col1, col2);
            }
            return resSum;
        }
    };

  • 0
    D

    good try! I noticed that you are using #rows segment trees. What I am thinking (and tried before) is to use one segment tree for the matrix. Concretely, I divide the matrix into four parts, left up, left bottom, right up, right bottom. And then the idea is similar.

    But you answered one big question, at least this problem can be solved by segment tree (other than binary indexed tree).


  • 0
    L

    @dachuan.huang The idea you mentioned is not 2D segment tree, but a quadtree. Quadtree has O(n) worst case complexity for range query, while true 2D segment tree gives O(logn * logn).


  • 0
    D

    @lcn I have found some opinion that is opposite to yours. https://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/25122078#25122078. This link told us that 2D segment tree is quad-tree.


Log in to reply
 

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