# Leetcode 307 Solution

https://leetcode.com/problems/range-sum-query-mutable

## Solution

``````class SegmentTree
{
int m_size;
vector<int> nodes;
public:
void init(int n)
{
m_size = n;
nodes.resize(2 * pow(2, ceil(log2(n))));
}

int getsize()
{
return m_size;
}

int build(vector<int>& nums, int i, int l, int r)
{
if (l == r)
return nodes[i] = nums[l];

int m = (l + r) / 2;
int left_sum = build(nums, 2 * i, l, m);
int right_sum = build(nums, 2 * i + 1, m + 1, r);
return nodes[i] = left_sum + right_sum;
}

int update(int i, int left, int right, int pos, int val)
{
if (left == right)
{
int res = val - nodes[i];
nodes[i] = val;
return res;
}

int m = (left + right) / 2;

int diff = pos <= m ? update(2 * i, left, m, pos, val) : update(2 * i + 1, m + 1, right, pos, val);
nodes[i] += diff;
return diff;
}

int query(int i, int left, int right, int l, int r)
{
if (left == l && right == r)
return nodes[i];

int m = (left + right) / 2;

int res = 0;
if (l <= m)
res += query(2 * i, left, m, l, min(m, r));
if (r > m)
res += query(2 * i + 1, m + 1, right, max(l, m + 1), r);
return res;
}
};

class NumArray {
SegmentTree st;
public:
NumArray(vector<int> nums) {
if (nums.size())
{
st.init(nums.size());
st.build(nums, 1, 0, nums.size() - 1);
}
}

void update(int i, int val) {
st.update(1, 0, st.getsize() - 1, i, val);
}

int sumRange(int i, int j) {
return st.query(1, 0, st.getsize() - 1, i, j);
}
};

/**
* 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);
*/
``````