|
导入:
考虑这样一个问题:
给出长度为n的序列,一共有m条cha询,每条cha询可能是下面两种中的一种:
1 l r cha询闭区间[l,r]的总和
2 l r k 把闭区间[l,r]的每一个数加上k
n,m均满足大于零不小于五十万
很容易想到下面这段代码:
变量名 | 类 型 | 静态 | 数组 | 备 注 | 序列 | 整数型 | | 0 | n | 整数型 | | | m | 整数型 | | | i | 整数型 | | | l | 整数型 | | | r | 整数型 | | | k | 整数型 | | | 答案 | 整数型 | | | 是否cha询总和 | 逻辑型 | | | 重定义数组 (序列, 假, n )计次循环首 (n, i ) 计次循环尾 ()计次循环首 (m, )判断 (是否cha询总和 ) 答案 = 0 变量循环首 (l, r, 1, i )答案 = 答案 + 序列 [i ]变量循环尾 () 变量循环首 (l, r, 1, i )序列 [i ] = 序列 [i ] + k 变量循环尾 ()计次循环尾 ()
这段代码思路非常清晰,它很好地模拟了每个操作,但是,太慢了。
如果n和m都给个五十万,就没法一秒搞定了哦~
PS:本题可以用树状数组写。
怎么办呢,我们就想是不是可以稍微优化一下。
引入概念:差分与前缀和。
差分:数组的第一个元素储存第一个元素,后面的元素储存这个元素与上一个元素的差。
栗子:1 2 3 4 5 存差分后=> 1 1 1 1 1
好处:方便区间修改,例如将栗子中的前四个元素加上3,只需要第一个(1=0+1)加3,第五个(5=4+1)减3就行了,我们试一试:
1(+3) 1 1 1 1(-3) => 4 1 1 1 -2 化为原数列=> 4 5 6 7 5
果然很方便,但是从这个过程中也稍微感受到了差分的不方便之处:虽然区间修改很快,但是如果我要知道其中的一个数,就不方便了,需要从头一直加到想要的那个数那里。因此,区间cha询并没有优势。
相反,前缀和就不一样,它刚好相反,看看它的定义~
前缀和:数组的每个元素储存数列的第一个元素到这个元素的总和。
仍然用上面的栗子:
1 2 3 4 5 存前缀和后=> 1 3 6 10 15
好处:cha询区间和非常方便。例如cha询[2,4]的总和,就用第4个元素减去第1个:10-1=9。
原理:第一个元素储存的是sum{1},第四个则是sum{1,2,3,4},相减就是想要的sum[2,4]啦~
糟糕的地方:区间修改就没那么快了。很显然,我们需要循环修改,没有性能优势。
以上介绍的两种优化,感兴趣的朋友们可以自己尝试一下~
有了这么多铺垫,终于要导出我们今天的主角——线段树了。
线段树的确是一棵树。它的每个节点都储存着区间信息。
由于我突然懒得画图了,而没得图线段树又讲不成,就先鸽着吧,反正我至今也没能用易语言写出能用的线段树。
|
评分
-
查看全部评分
|