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