Segment tree in C++, but 1720 is toooooo long ...


  • 0
    G
    class NumArray {
    private:
    	vector<int> _nums;
    	int _base;
    	int _original;
    
    public:
    	NumArray(vector<int> &nums) 
    	{
    		int k = 0;
    		while ((1 << k) < nums.size())
    		{
    			k++;	
    		}
    
    		vector<int> buf((1 << (k+1))-1, 0);
    		int base = (1 << k)-1;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			buf[i + base] = nums[i];
    		}
    
    		_original = nums.size();
    		_base = base;
    		_nums = buf;
    
    		for (int i = base-1; i >= 0; i--)
    		{
    			_nums[i] = _nums[i * 2 + 1] + _nums[i * 2 + 2];
    		}
    	}
    
    	void update(int i, int val) 
    	{
    		if (i >= 0 && i < _original)
    		{
    			_nums[i + _base] = val;
    
    			int k = i+_base;
    			while (k>0)
    			{
    				k = (k-1) / 2;
    				_nums[k] = _nums[k * 2 + 1] + _nums[k * 2 + 2];
    			}
    		}
    	}
    
    	int sumRange(int i, int j) 
    	{
    		return sum(i, j, 0, 0, _base);
    	}
    
    	int sum(int i, int j, int index,int x, int y)
    	{
    		if (i <= x && j >= y)
    		{
    			return _nums[index];
    		}
    
    		if (y<i || x>j) return 0;
    
    		int m = (y - x) / 2+x;
    
    		int r1 = sum(i, j, index * 2 + 1, x, m);
    		int r2 = sum(i, j, index * 2 + 2, m + 1, y);
    
    		return r1 + r2;
    	}
    };

  • 0
    J

    My C++ execution time is 1816ms and I cannot find out how to optimize either.


Log in to reply
 

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