当前位置:首页 > 数据结构 > 树状数组 > 正文
SSOJ2613单点修改区间求和
3645+

题目大意:有n个数,不断地对其中的某个数字进行修改,不断地询问某一段数字的和,如何快速解决?

题目描述

给你n个整数,请问第x个到第y个的和是多少?

与上一题不同,在询问前后,这n个数中的某个数可能会有改动。

输入

第一行:n和m,表示n个数,m个询问

第二行:n个整数

接下来m行,每行3个整数o、x、y:o表示求和还是更改数字,如果o=1,表示将第x个数改成y;如果o=2,表示求第x个到第y个的和。

输出

对于每次询问和,输出区间的和。

样例输入

5 3
1 2 -3 6 5
2 2 4
1 2 5
2 1 3

样例输出

5
3

提示

1<=x、y<=n;1<=o<=2;n个数,每个数的绝对值不超过1000;5<=n、m<=200000

(10个点数据范围:5, 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 150000, 200000)

解题思路

读入n个数到数组a,对于每次询问,如果是修改,则直接修改a[i]的值,如果是询问区间和,值直接累加区间所有元素,时间复杂度O(m*n),不能拿满分。

程序慢在区间求和,如果用上一题的思想,记录前缀和的话,那么更新一个元素的值,还是需要O(n)更新元素后面的所有前缀和,时间复杂度并没有改变。

如何让更新元素的值时更新和比较快,而且求连续子段和也比较快呢?分块!前缀和是分成1个一块、2个一块、3个一块、……、n个一块,这样的块太多太长,更新起来比较慢。我们可以换一种方法分块:分成√n块,每块有√n个,这样更新的时候,只需要修改一块的和,时间复杂度是O(1);求和的时候,如果区间包含一整块,就直接加一整块,不是一整块就逐个加起来(非一整块的在两端,加起来不超过2*√n,中间不超过√n块),时间复杂度是O(√n)。这样总体时间复杂度就是O(m*√n)。

思考:如何判断一个元素属于哪一块?

回答:每块有p个(p=√n),元素除以p相同即同一块,这样每一块恰好p个(从0开始的话)。

求和的时候,要加√n块,√n个元素,比较耗时,能不能再快一点呢?可以,只要分块分得更加巧妙——利用二进制的思想!分块的时候,每一块都是2^k次方个(k是自然数),如果求前面y个的和,那么将长度为y的序列拆分成若干个含有2^k个元素的小块:如y=6,二进制下是110,那么拆分成5-6和1-4两块;又如y=10,二进制下是1010,那么拆分成9-10和1-8两块;又如y=15,二进制下是1111,那么拆分成15-15、13-14、9-12、1-8四块;又如32,二进制下是100000,那么拆分成1-32一块。这样,即使是一个很大的数y=123456,二进制下是1 1110 0010 0100 0000,也就分成6块,从左到右每块依次长度为2^16、2^15、2^14、2^13、2^9、2^6,求和时只需要加6次,任意一个数至多分成log2n块,也即最多加log2n次

那么,如何记录每一小块的和呢?我们用c数组记录小块的和,c[i]表示以i结尾,连续2^k个元素的和,那么k是多少呢?

s[i]表示前i个的和,那么s[123456] = c[123456] + c[123456-2^6] + c[123456-2^6-2^9] + c[123456-2^6-2^9-2^13] + c[123456-2^6-2^9-2^13-2^14] + c[123456-2^6-2^9-2^13-2^14-2^15],再举个简单的例子,y=6,二进制下是110,那么拆分成5-6和1-4两块,s[6] = c[6] + c[6-2^1] = c[6] + c[4] = a[5]+a[6] + a[1]+a[2]+a[3]+a[4],也就是说c[6]记录的是左边离他最近的2个数的和,c[4]记录的是左边离他最近的4个数的和。那么c[i]是离他最近的几个数的和?最右边的那个1!c[6]之所以表示最近的2个,是因为110分成100和10两块,10是接近6的那一块;c[123456]之所以表示最近的2^6个,是因为1 1110 0010 0100 0000分成1 0000 0000 0000 0000、1000 0000 0000 0000、100 0000 0000 0000、10 0000 0000 0000、10 0000 0000、100 0000共6块,100 0000是接近123456的那一块。加了y最右边那一块之后,那么还需要求前面y-2^k个的和,即求前面那些小块的和。如果是6的话,那么要从c[6]跳到c[4](因为已经加了2个的和了,所有6-2=4)。

求和的问题解决了,c[i]表示什么也确定了,那么更新的时候如何更新呢?如我要更新a[1],那么含有a[1]的块有哪些?也就是需要更新和的块有哪些?二进制下,1的二进制是1,被1、10、100、1000等包含(101仅包含101这个元素、110近包含110和101两个元素),故需要更新c[1]、c[2]、c[4]、c[8]……那么更新a[5]呢?5的二进制是101,被101、110、1000、10000等包含(110包含110和101两个元素),故需要更新c[5]、c[6]、c[8]、c[16]……不难发现,1、2、4、8以及5、6、8、16的变化规律就是前一个数加上最右边的那个1,因为这个1管的就是自己前面2^k次方个元素的和。

读入数据以及修改数据的时候,更新包含该元素的块的和;求和区间[x, y]的和的时候,用前y个的和减去前x-1个的和即可,时间复杂度O(m*log2n)。

程序实现

树状数组O(mlog2n):

分块O(m√n):

暴力70分O(mn):

===================线段树做法===================

结构体存储,记录区间端点、左右儿子、线段和:

不难发现,在递归的过程中,区间端点是可以算出来的,不需要记录:

堆结构存储,不需要记录左右儿子是谁,结点p的左儿子是p*2,右儿子是p*2+1,数组大小1<<⌈log2n⌉+1,具体请看下一篇文章:

堆结构存储,最后一层可能空很多,浪费空间,可以使用更紧凑的存储方式:叶子节点分别存在编号为2、4、6、……、2n位置,父亲结点存储在儿子结点的中间位置,如果是偶数就+1变成奇数,达到每个结点都有自己的固定位置,区间[l,r]的位置计算方法:(l+r)|(l!=r),非叶子结点|1总会是奇数。

SSOJ2613单点修改区间求和:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!