# 56 ms C++ segment tree solution

• For segment tree, see https://en.wikipedia.org/wiki/Segment_tree. And useful link https://en.wikipedia.org/wiki/Range_minimum_query

`````` class NumArray {
vector<int> nums;
vector<int> memo;
int buildSegmentTree(int idx, int l, int h) {
if (l == h) {
memo[idx] = nums[l];
return memo[idx];
}
int m = l + (h - l) / 2;
int left = buildSegmentTree(2 * idx + 1, l, m);
int right = buildSegmentTree(2 * idx + 2, m + 1, h);
memo[idx] = left + right;
return memo[idx];
}
int query(int i, int j, int l, int h, int idx) {
if (i > h || j < l) {
return 0;
}
if (i <= l && j >= h) {
return memo[idx];
}
int m = l + (h - l) / 2;
int left = query(i, j, l, m, 2 * idx + 1);
int right = query(i, j, m + 1, h, 2 * idx + 2);
return left + right;
}
void updateInternal(int i, int l, int h, int idx, int diff) {
if (i < l || i > h) {
return;
}
if (l == h) {
if (i == l) memo[idx] += diff;
return;
}
if (i >= l && i <= h) {
memo[idx] += diff;
}
int m = l + (h - l) / 2;
updateInternal(i, l, m, idx * 2 + 1, diff);
updateInternal(i, m + 1, h, idx * 2 + 2, diff);
}
public:
NumArray(vector<int> &nums) {
this->nums = nums;
int n = nums.size();
if (n > 0) {
int lgn = ceil(log2(n)) + 1;
memo.resize(1 << lgn, 0);
buildSegmentTree(0, 0, n - 1);
}
}

void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
updateInternal(i, 0, nums.size() - 1, 0, diff);
}

int sumRange(int i, int j) {
return query(i, j, 0, nums.size() - 1, 0);
}
};``````

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