15-liner C++ "segment tree" by using array of size 2*N


  • 0

    No need to actually build a segment tree. Just need an array of size 2*N (similar to heap)

    class NumArray {
    
    private:
        vector<int> _data;
        int _n;
        
    public:
        NumArray(vector<int> nums):_n(nums.size()) {
            if (!_n) return;
                    
            // build "segment tree"
            _data.resize(2*_n);
            int i = _n;
            while (--i >= 0) _data[i+_n] = nums[i];
            i = _n;
            while (--i) _data[i] = _data[2*i] + _data[2*i+1];
            
        }
        
        void update(int i, int val) {
            if (!_n) return;
            _data[i += _n] = val;
            while (i /= 2) _data[i] = _data[2*i] + _data[2*i+1];
        }
        
        int sumRange(int i, int j) {
            int sum = 0;
            if (!_n) return sum;
            
            for (i += _n, j += _n; i <= j; i /= 2, j /= 2) {
                if (i%2) sum += _data[i++];            
                if (j%2 == 0) sum += _data[j--];            
            }
            return sum;
        }
    };
    

Log in to reply
 

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