利用树状数组解决几类问题 浙江省温岭中学 林希 树状数组作为一种实现简单、应用较广的高级数据结构，在 OI 界的地位越来越重要，下面我来简单介绍一下树状数组和它的简单应用。 一、树状数组简介 树状数组(Binary Indexed Trees，简称 BIT)是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。它可以方便地查询出一段区间中的数字之和。其查询和修改的时间复杂度均为O(lbN),并且是一个在线的数据结构，可以随时修改并查询。我接下来用一道题目来介绍树状数组的几个基本操作。 【引例】 假设有一列数{ Ai} （1<=i<=n），支持如下两种操作： 1. 将 Ak 的值加 D。（k，D 是输入的数） 2. 输出tsiiA （s，t 都是输入的数，s<=t） 这道题目用线段树很容易可以解决，我就不多说了，那么如何用树状数组来解决呢？我们新增一个数组C[]，其中C[i]=a[i-2k+1]+……+a[i](k 为i 在二进制形式下末尾 0 的个数)。根据定义我们可以得出一下这张表格： i 二进制 K 1 (1)2 0 c[1]=a[1] 2 (10) 2 1 c[2]=a[1]+a[2]=c[1]+a[2] 3 (11) 2 0 c[3]=a[3] 4 (100) 2 2 c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] 5 (101) 2 0 c[5]=a[5] 6 (110) 2 1 c[6]=a[5]+a[6]=c[5]+a[6] „„ 在这里，我们会发现k 值的求解会有一些难度，这就引出了树状数组的第一个操作：低位技术，也叫 Low bit(k)。 对于 Lowbit 这里我提三种不同的写法（这三种形式是等价的，读者有兴趣可以去证明一下）： 1.Lowbit(k)=k and (k or (k-1)) 2.Lowbit(k)=k and not (k-1) 3.Lowbit(x)=k and –k 然后我来分析引例的树状数组解法，为了可以更好地理解这种方法，读者可以根据以下这幅图来加以理解。 【操作2 】修改操作：将Ak 的值加D 可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(lbN)。 定理1：若A[k]所牵动的序列为C[p1]，C[p2]……C[pm]， 则p1=k，而iliipp21（li 为pi 在二进制中末尾０的个数）。 例如A[1]……A[8]中，a[3] 添加x； p1=k=3 p2=3+20=4 p3=4+22=8 p4=8+23=16>8 由此得出，c[3]、c[4]、c[8]亦应该添加x。 定理的证明如下： 【引 理】若A[k]所牵动的序列为C[p1]，C[p2] „„ C[pm]， 且p1
