bit.cpp(树状数组基本框架):
树状数组是一类比较简单的数据结构,和线段树比较像。树状数组是维护前缀和的一种数据结构。这就导致它能用较短的时间来实现查询和改变值。
树状数组比线段树、平衡树要容易写,代码复杂度低。但不足的是适用面较窄(空间消耗大)。有句话是这样说的:能用树状数组的就能用线段树,能用线段树的就能用平衡树。
所以一般都是能用线段树就不用平衡树,能用树状数组就不用线段树。(从这其实就可以知道树状数组的魅力有多大了)
【树状数组介绍】
首先,先要理解树状数组的含义。含义其实就是用一个数组,构成树形结构来维护原数组的前缀和。
显然,对于树状数组C,C[I]对应“管辖”多少个元素,与它对应二进制数最右端第一个1的位置有关。这样,就能够达到询问一个区间的值,或者改变值的时间代价为LogN。
对于树状数组,就只有这么些函数(所以代码就比较少)。但树状数组的神奇之处就在于这三个函数了。(本质只有两个)仅仅就是这三个函数,但这就是树状数组的看家本领了。用好这三个函数,也就能解决比较多的问题。