树状数组小结

BIT(Binary Indexed Tree),简单总结一下。

常用模型:1.增加某个位置的值并求区间和/最大值。 2.静态求多个区间的最值。

基本思想就是:每个整数都能表示为一些2的幂次方的和,比如13,其二进制表示为1101,所以它能表示为: 13 = 2^0 + 2^2 + 2^3 .类似的,累积频率可表示为其子集合之和。在本文的例子中, 每个子集合包含一些连续的频率值,各子集合间交集为空。在二进制表示中,13=1101。因此, 我们可以这样计算:c[1101]=tree[1101]+tree[1100]+tree[1000]

其中tree的索引idx规律如下:当idx>0时,重复以下操作:sum加上tree[idx], 然后将idx最后的1去掉。

因为tree数组是这么定义的: tree[idx] = f[idx-2^r +1] +…+ f[idx]. 上面的程序sum加上tree[idx]后, 去掉idx最后的1,假设变为idx1,那么有idx1 = idx-2^r , sum接下来加上tree[idx1] = f[idx1-2^r1 +1] +…+ f[idx1] = f[idx1-2^r1 +1] +…+ f[idx-2^r ], 我们可以看到tree[idx1]表达示的最右元素为f[idx-2^r ],这与tree[idx]表达式的最左元 素f[idx-2^r +1]无缝地连接了起来。所以,只需要这样操作下去,即可求得f[1]+…+ f[idx],即c[idx]的结果。下面的例子有助于我们的理解:

tree[1101]=f[13]
tree[1100]=f[9]+…+f[12]
tree[1000]=f[1]+…+f[8]
c[1101]=f[1]+…+f[13]=tree[1101]+tree[1100]+tree[1000]

核心代码:

题目1:小朋友排队

实际上是求逆序对的变种。对于每个小朋友,我们考虑的是需要交换多少次,与逆序对不同的是,交换的两个数都要算,且次数时需要知道的,所以对于每个小朋友考虑左边比他大的和右边比他小的就好了。注意点就是我们在求逆序对的树状数组的时候,存入的是数组里的值,因此树状数组的范围的上限是最大数,为了保证下限是1(因为我正常是从1写的),我们需要把小朋友的身高加一进行保存。

主要代码:

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注