LintCode 207. 区间求和 II（线段树）

样例1
输入:
[1,2,7,8,5]
[query(0,2),modify(0,4),query(0,1),modify(2,1),query(2,4)]
输出: [10,6,14]
说明:
给定数组 A = [1,2,7,8,5].
在query(0, 2)后, 1 + 2 + 7 = 10,
在modify(0, 4)后, 将 A[0] 修改为 4， A = [4,2,7,8,5].
在query(0, 1)后, 4 + 2 = 6.
在modify(2, 1)后, 将 A[2] 修改为 1，A = [4,2,1,8,5].
After query(2, 4), 1 + 8 + 5 = 14.

样例2
输入:
[1,2,3,4,5]
[query(0,0),query(1,2),quert(3,4)]
输出: [1,5,9]
说明:
1 = 1
2 + 3 = 5
4 + 5 = 9

挑战
query 和 modify 的时间复杂度需要为O(logN).

class node
{
public:
    int sum;
    int start, end;
    node *left, *right;
    node(int s, int e, int v):start(s),end(e),sum(v)
    {
        left = right = NULL;
    }

    static node* build(vector<int>& A, int l, int r)
    {
        if(l > r)
            return NULL;
        node* head = new node(l,r,A[l]);
        if(l == r)
            return head;
        int mid = l+((r-l)>>1);
        head->left = build(A,l,mid);
        head->right = build(A,mid+1,r);
        head->sum = 0;
        if(head->left)
            head->sum += head->left->sum;
        if(head->right)
            head->sum += head->right->sum;
        return head;
    }

    static long long query(node* head, int s, int e)
    {
        if(s > head->end || e < head->start)
            return 0;
        if(head->start >= s && head->end <= e)
            return head->sum;
        int vl = query(head->left, s, e);
        int vr = query(head->right,s, e);
        return vl+vr;
    }

    static void modify(node* head, int id, int val)
    {
        if(head->start == head->end)
        {
            head->sum = val;
            return;
        }
        int mid = (head->start + head->end)/2;
        if(id > mid)
            modify(head->right, id, val);
        else
            modify(head->left, id, val);
        head->sum = 0;
        if(head->left)
            head->sum += head->left->sum;
        if(head->right)
            head->sum += head->right->sum;
    }
};
class Solution {
    node *head;
public:
    Solution(vector<int> A) {
        head = node::build(A,0,A.size()-1);
    }

    long long query(int start, int end) {
        return node::query(head, start,end);
    }

    void modify(int index, int value) {
        node::modify(head, index,value);
    }
};