树状数组维护区间和的模型及其拓广的简单总结

树状数组维护区间和的模型及其拓广的简单总结 by wyl8899 树状数组的基本知识已经被讲到烂了,我就不多说了,下面直接给出基本操作的代码。 假定原数组为a[1..n],树状数组b[1..n],考虑

树状数组维护区间和的模型及其拓广的简单总结 bywyl8899 树状数组的基本知识已经被讲到烂了,我就不多说了,下面直接给出基本操作 的代码。 假定原数组为a[1..n],树状数组b[1..n],考虑灵活性的需要,代码使用 int*a传数组。#definelowbit(x)((x)&(-(x))) intsum(int*a,intx){ ints=0; for(;x;x-=lowbit(x))s+=a[x]; returns; } voidupdate(int*a,intx,intw){ for(;x<=n;x+=lowbit(x))a[x]+=w; } sum(x)返回原数组[1,x]的区间和,update(x,w)将原数组下标为x的数加上 w。 这两个函数使用O(操作数*logn)的时间和O(n)的空间完成单点加减,区间求 和的功能。 接下来做一些升级,让树状数组完成区间加减,单点查询的功能。