Class NumArray

templates/segment-tree.cpp:8–108

@lc code=start

// @lc code=start
class NumArray {
public:
    struct TreeNode{
        int l, r, v;
        TreeNode * left = nullptr;
        TreeNode * right = nullptr;
        TreeNode(int l, int r, int v):l(l), r(r), v(v){

        }
        TreeNode(int l, int r, int v, TreeNode * left, TreeNode * right):l(l), r(r), v(v),
            left(left), right(right)
        {

        }
    };

    TreeNode * root;

    TreeNode * buildTree(vector<int>& nums, int l, int r)
    {
        if(l == r){
            // 叶子节点
            return new TreeNode(l, r, nums[l]);
        }

        // 后序构造
        auto left = buildTree(nums, l, (l+r)/2);
        auto right = buildTree(nums, (l+r)/2+1, r);

        // 非叶子节点
        return new TreeNode(l, r, left->v+right->v, left, right);
    }

    void dumpInternal(TreeNode * n, int d){
        if(!n)return;
        for(int i=0; i<d; i++)printf("--");
        printf("%d(%d %d)\n", n->v, n->l, n->r);
        dumpInternal(n->left, d+1);
        dumpInternal(n->right, d+1);
    }

    void updateNode(TreeNode * n, int pos, int val){
        if(!n)return;

        if(n->l == n->r && n->l == pos){
            n->v = val;
            return;
        }

        int m = (n->l+n->r)/2;

        // 后序遍历
        if(pos <= m){
            updateNode(n->left, pos, val);
        }else{
            updateNode(n->right, pos, val);
        }
        n->v = n->left->v + n->right->v;