线段树的作用

线段树是一种二叉搜索树,它能以较低时间复杂度O(logN)得解决大规模求和、gcd等
空间复杂度为2N，但实际应用时还需4N的空间

查询和单点更改的代码实现

class NumArray
{
  public:
    int *tree;
    int size;

    NumArray(vector<int> nums)
    {
        size = nums.size();
        //size储存原始数据的数量
        tree = new int[size * 4];
        if (size != 0)
            Build(1, size, 1, nums);
        //以1为根节点，为了防止计算问题而废除0号位置
    }

线段树大小为原始数组大小的4倍

==>Q:树叶节点和树节点一共2n个数据，为什么需要4倍?
==>A:在递归时候仍然需要访问叶子节点下一层子树，下一层子节点一共有2n个，所以共计4n的空间需求

void Build(int left, int right, int index, vector<int> &nums)
{
    if (left == right) //如果到达叶子节点不再向下访问
    {
        tree[index] = nums[left - 1];
        //==>Q:为什么需要访问nums[left-1]而不是nums[left]?
        //==>A:tree数组以1位开始为第一个数据，而传入的数组是以0位为第一个数据
        return;
    }
    int mid = (left + right) / 2;
    Build(left, mid, 2 * index, nums);
    Build(mid + 1, right, 2 * index + 1, nums);
    PushUp(index);
    //建完左右子树后更新自己的数据
}

==>Q:为什么左右节点的序号分别是2n和2n+1?
==>A:见下图

               1
              (1)
        2             3
      (2*1)        (2*1+1)
    4       5     6       7
  (2*2)  (2*2+1)(2*3)  (2*3+1)

…continue

这种编号顺序无浪费而且易知根节点为index/2

void PushUp(int index)
{
    tree[index] = tree[2 * index] + tree[2 * index + 1];
    //根数据=左数据+右数据
}

void Update(int position, int val, int left, int right, int index)
{
    if (left == right) //如果到达叶子节点不再向下访问
    {
        tree[index] = val;
        //叶子节点值更改
        return;
    }
    int mid = (left + right) / 2;
    if (position <= mid) //算是一种二分查找,需要更改的位置在二分后是中值的左或者右边
        Update(position, val, left, mid, index * 2);
    //如果更改在中值左侧就访问左子树
    else
        Update(position, val, mid + 1, right, index * 2 + 1);
    //如果更改在中值右侧就访问右子树
    PushUp(index);
    //更新自己的数据,使更改一层层加起来
}

int Query(int Left, int Right, int left, int right, int index)
{
    if (Left <= left && right <= Right)
    //如果数据值在所求区域内....[Left..[left.......right]......Right]....
    {
        return tree[index];
        //返回我的数据,不再递归
    }
    int mid = (left + right) / 2;
    int ans = 0;
    if (Left <= mid) //如果中值>=所求区域左临界
        ans += Query(Left, Right, left, mid, index * 2);
    if (Right >= mid + 1) //如果中值+1<=所求区域右临界
        ans += Query(Left, Right, mid + 1, right, index * 2 + 1);
    return ans;
}
                  [1  2  3  4  5  6  7  8  9  10  11  12  13]   => 求[4,12]
                  [1  2  3  4  5  6  7][8  9  10  11  12  13]
                  [1  2  3  4][5  6  7][8  9  10][11  12  13]
                        [3  4]   XXX      XXX    [11  12]
                           [4]                     XXX
                           XXX

XXX表示返回上一个节点的数据不再递归
[4,12]==>[4] + [5,7] + [8,10] + [11,12]
在[1 2 3 4]被拆分为[1 2][3 4]时由于mid=2<3故不再访问左子树[1 2]
[13],[3]同理
在[1 2 3 4 5 6 7]被拆分为[5 6 7]时由于 5>3 && 8<12 则直接返回其数据不再递归
[8 9 10 11]同理

    void update(int i, int val)
    {
        Update(i + 1, val, 1, size, 1);
        //程序查询时候从0开始计位,故需要加一,从[1,size]中递归更改值
    }

    int sumRange(int i, int j)
    {
        return Query(i + 1, j + 1, 1, size, 1);
        //程序查询时候从0开始计位,故需要加一,从[1,size]中递归查找结果值
    }
};