C++, Segment Tree,update and sum are both O(logn)


  • 20
    S
    struct SegmentTreeNode {
        int start, end, sum;
        SegmentTreeNode* left;
        SegmentTreeNode* right;
        SegmentTreeNode(int a, int b):start(a),end(b),sum(0),left(nullptr),right(nullptr){}
    };
    class NumArray {
        SegmentTreeNode* root;
    public:
        NumArray(vector<int> &nums) {
            int n = nums.size();
            root = buildTree(nums,0,n-1);
        }
       
        void update(int i, int val) {
            modifyTree(i,val,root);
        }
    
        int sumRange(int i, int j) {
            return queryTree(i, j, root);
        }
        SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) {
            if(start > end) return nullptr;
            SegmentTreeNode* root = new SegmentTreeNode(start,end);
            if(start == end) {
                root->sum = nums[start];
                return root;
            }
            int mid = start + (end - start) / 2;
            root->left = buildTree(nums,start,mid);
            root->right = buildTree(nums,mid+1,end);
            root->sum = root->left->sum + root->right->sum;
            return root;
        }
        int modifyTree(int i, int val, SegmentTreeNode* root) {
            if(root == nullptr) return 0;
            int diff;
            if(root->start == i && root->end == i) {
                diff = val - root->sum;
                root->sum = val;
                return diff;
            }
            int mid = (root->start + root->end) / 2;
            if(i > mid) {
                diff = modifyTree(i,val,root->right);
            } else {
                diff = modifyTree(i,val,root->left);
            }
            root->sum = root->sum + diff;
            return diff;
        }
        int queryTree(int i, int j, SegmentTreeNode* root) {
            if(root == nullptr) return 0;
            if(root->start == i && root->end == j) return root->sum;
            int mid = (root->start + root->end) / 2;
            if(i > mid) return queryTree(i,j,root->right);
            if(j <= mid) return queryTree(i,j,root->left);
            return queryTree(i,mid,root->left) + queryTree(mid+1,j,root->right);
        }
    };
    
    
    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.update(1, 10);
    // numArray.sumRange(1, 2);

  • 1
    H

    very good solution!!!


  • 0
    This post is deleted!

  • 1
    R

    This solution is not getting accepted.
    Gives error: Line 111: invalid initialization of non-const reference of type 'std::__debug::vector<int>&' from an rvalue of type 'std::__debug::vector<int>'


  • 0

    Segment Tree using vectors (130ms)

    class NumArray {
    public:
        int len=0;
        vector<int> dup;
        vector<int> seg;
        // qsum -> calculates sum between the given range
        int qsum(vector<int> &seg,int &qlow,int &qhigh,int low,int high,int pos){
            if(qlow <= low && qhigh >= high) return seg[pos];
            if(low>qhigh ||high<qlow) return 0;
            int mid = low + (high-low)/2;
            return qsum(seg,qlow,qhigh,low,mid,2*pos+1) + qsum(seg,qlow,qhigh,mid+1,high,2*pos+2);
        }
        // segpopulate -> populates the segment tree
        void segpopulate(vector<int> &nums,vector<int> &seg,int low,int high,int pos){
            if(high == low) {seg[pos] = nums[low]; return;} 
            int mid  = low + (high-low)/2;
            segpopulate(nums,seg,low,mid,2*pos+1);
            segpopulate(nums,seg,mid+1,high,2*pos+2);
            seg[pos] = seg[2*pos+1] + seg[2*pos+2];
        }
        //  modify -> makes changes to segment tree
        void modify(vector<int> &seg,int low,int high, int &index, int &target,int pos){
            if(low <= index && high >= index) seg[pos] = seg[pos]+target;
            if(low == high) return;
            if(low>index ||high<index) return ;
            int mid = low + (high-low)/2;
            modify(seg,low,mid,index,target,2*pos+1);
            modify(seg,mid+1,high,index,target,2*pos+2);
        }
        NumArray(vector<int> nums) {
            dup = nums;
            len = nums.size();
            if(len ==0) return;
            int s = log2(len);
            if(pow(2,s)!= len) s++;
            s = pow(2,s);
            s = 2*s -1;
            seg = vector<int>(s,0);
            segpopulate(nums,seg,0,nums.size()-1,0);
        }
        
        void update(int i, int val) {
            int diff = val - dup[i];
            dup[i] = val;
            modify(seg,0,len-1,i,diff,0);
        }
        
        int sumRange(int i, int j) {
            return qsum(seg,i,j,0,len-1,0);
        }
    };
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * obj.update(i,val);
     * int param_2 = obj.sumRange(i,j);
     */
    

  • 0
    W

    You have an error in your code, NumArray should take "vector<int> nums" as the parameter instead of "vector<int> &nums".


  • 0
    T

    shouldnt update propogate change in sum down the chain as well ? say if we update root->left and root sum should also change since it is sum of left and right sum?


  • 0
    G

    @shuai9 said in C++, Segment Tree,update and sum are both O(logn):

    struct SegmentTreeNode {
    int start, end, sum;
    SegmentTreeNode* left;
    SegmentTreeNode* right;
    SegmentTreeNode(int a, int b):start(a),end(b),sum(0),left(nullptr),right(nullptr){}
    };
    class NumArray {
    SegmentTreeNode* root;
    public:
    NumArray(vector<int> &nums) {
    int n = nums.size();
    root = buildTree(nums,0,n-1);
    }

    void update(int i, int val) {
        modifyTree(i,val,root);
    }
    
    int sumRange(int i, int j) {
        return queryTree(i, j, root);
    }
    SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) {
        if(start > end) return nullptr;
        SegmentTreeNode* root = new SegmentTreeNode(start,end);
        if(start == end) {
            root->sum = nums[start];
            return root;
        }
        int mid = start + (end - start) / 2;
        root->left = buildTree(nums,start,mid);
        root->right = buildTree(nums,mid+1,end);
        root->sum = root->left->sum + root->right->sum;
        return root;
    }
    int modifyTree(int i, int val, SegmentTreeNode* root) {
        if(root == nullptr) return 0;
        int diff;
        if(root->start == i && root->end == i) {
            diff = val - root->sum;
            root->sum = val;
            return diff;
        }
        int mid = (root->start + root->end) / 2;
        if(i > mid) {
            diff = modifyTree(i,val,root->right);
        } else {
            diff = modifyTree(i,val,root->left);
        }
        root->sum = root->sum + diff;
        return diff;
    }
    int queryTree(int i, int j, SegmentTreeNode* root) {
        if(root == nullptr) return 0;
        if(root->start == i && root->end == j) return root->sum;
        int mid = (root->start + root->end) / 2;
        if(i > mid) return queryTree(i,j,root->right);
        if(j <= mid) return queryTree(i,j,root->left);
        return queryTree(i,mid,root->left) + queryTree(mid+1,j,root->right);
    }
    

    };

    // Your NumArray object will be instantiated and called as such:
    // NumArray numArray(nums);
    // numArray.sumRange(0, 1);
    // numArray.update(1, 10);

    I just copy and paste this code and get an error "Line 110: invalid initialization of non-const reference of type 'std::vector<int>&' from an rvalue of type 'std::vector<int>'".
    Can anybody explain why?


Log in to reply
 

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