线段树的作用

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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的空间需求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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]同理

1
2
3
4
5
6
7
8
9
10
11
12
    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]中递归查找结果值
}
};