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

• ``````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;
}
};``````

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

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