线段树

给定一个数组nums，之后若干操作，操作一是更改数组中一个元素的值，操作二是获取nums[left,right+1]的总和。
方法一：分块处理。该方法的精华在于如何确定块的大小，设块的大小是size，则块的数量是n/size，计算子区间和时时间复杂度O(size+n/size)，由均值定理得，size+n/size在size取$\sqrt{n}$时取最小值。然后nums[0:size]的和是sums[0]，nums[size:2*size]的和是sums[1]，依此类推，以块为单位做映射。
方法二：线段树。如下代码比较好理解，且我想把它当作使用线段树解题的模板。

class NumArray {
public:
    int *tree;
    int n;
    NumArray(vector<int>& nums) {
        n = nums.size();
        tree = new int[2*n];
        int i,j;
        for(i=n,j=0;i<2*n;i++,j++)
            tree[i] = nums[j];
        for(j=n-1;j>0;j--)
            tree[j] = tree[2*j] + tree[2*j+1];
    }
    
    void update(int i, int val) {
        int pos = i+n;
        tree[pos] = val;
        int left,right;
        while(pos)
        {
            left = pos;
            right = pos;
            if(pos&1)
                left = pos - 1;
            else right = pos + 1;
            pos>>=1;
            tree[pos] = tree[left] + tree[right];
        }
    }
    
    int sumRange(int i, int j) {
        int sum  = 0;
        i+=n;j+=n;
        while(i<=j)
        {
            if(i&1)
            {
                sum += tree[i];
                i++;
            }
            if(!(j&1))
            {
                sum += tree[j];
                j--;
            }
            i>>=1;
            j>>=1;
        }
        return sum;    
    }
};

上述线段树的代码来自昵称可以随便改的鸭
方法三：前缀和，前n项和的数组。但由于更新值的时间复杂度为O(n)，目前在力扣运行会超时

参考链接：307. 区域和检索 - 数组可修改

创建于2022.4.22/15.46，修改于2022.4.22/15.46

#segment-tree