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?


  • 1
    C

    Even though changed the & in vector<int>&nums, it is still TLE. Any idea?


  • 0
    P

    Why TLE??
    I don't find any difference .Isn't the Time Complicity O(lgN)?????

    class NumArray {
    struct TreeNode {
        int val;
        int l;
        int r;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x,int s,int e) : val(x),l(s),r(e), left(NULL), right(NULL) {}
    };
        TreeNode* root;
        TreeNode* BuildHelper(vector<int>nums,int s,int e)
        {
            if(s>e) return NULL;
            if(s==e)
            {
                TreeNode* node= new TreeNode(nums[s],s,e);
                return node;
            }
            TreeNode* node = new TreeNode(0,s,e);
            int m=(s+e)>>1;
            node->left=BuildHelper(nums,s,m);
            node->right=BuildHelper(nums,m+1,e);
            int l=(node->left==NULL?0:node->left->val);
            int r=(node->right==NULL?0:node->right->val);
            node->val=l+r;
            return node;
        }
        int sumRange(TreeNode* node,int l,int r)
        {
            if(node==NULL) return 0;
            if(node->l>=l&&node->r<=r) return node->val;
            else if(node->r<l) return 0;
            else if(node->l>r) return 0;
            else
            {
                int m=(node->l+node->r)/2;
                if(l>m) return sumRange(node->right,l,r);
                else if(r<=m) return sumRange(node->left,l,r);
                else return sumRange(node->left,l,r)+sumRange(node->right,l,r);
            }
        }
        int update(TreeNode* node,int i,int val)
        {
            if(node==NULL) return 0;
            if(node->l==node->r&&node->l==i)
            {
                int diff=val-node->val;
                node->val=val;
                return diff;
            }else if(node->left&&node->left->l<=i&&node->left->r>=i)
            {
                int diff=update(node->left,i,val);
                node->val+=diff;
                return diff;
            }else if(node->right&&node->right->l<=i&&node->right->r>=i)
            {
                int diff=update(node->right,i,val);
                node->val+=diff;
                return diff;
            }
            return 0;
        }
    public:
        NumArray(vector<int> nums) {
            root=BuildHelper(nums,0,nums.size()-1);
        }
    
        void update(int i, int val) {
            update(root,i,val);
        }
    
        int sumRange(int i, int j) {
            return sumRange(root,i,j);
        }
    };

  • 0
    P

    @ChemyHusky
    @puzeyu
    SegmentTreeNode* buildTree(vector<int> &nums, int start, int end)

    don't delete this &


Log in to reply
 

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