来看一个问题：给出一个非负整数序列A，元素个数为N(N≤10^5, A[i]≤10^5)，在有可能随时添加或删除元素的情况下，实时查询序列元素第K大，即把序列元素从小到大排序后从左到右的第K个元素。

一般来说，如果在查询的过程中元素可能发生改变（例如插入、修改或删除），就称这种查询为在线查询；如果在查询过程中元素不发生改变，就称为离线查询。显然，上面的序列元素第K大的问题是在线查询，如果直接暴力做，在添加跟删除元素时就要有O(n)的时间复杂度来移动序列的元素，效率极其低下。事实上，序列元素第K大有很多解决方法，本节将介绍其中较容易理解、写法也很简洁的一种做法，即分块的思想。

一般而言，为了达到高效的目的，对一个有N个元素的有序序列，除最后一块外，其余每块中元素的个数都应当为(floor(N开根号)，floor为向下取整)，于是有序序列被划分为(ceil(N开根号)，ceil为向上取整)。

考虑到序列中的元素都是不超过10^5的非负整数，因此不妨设置一个hash数组table[1OOOO1]，其中table[x]表示整数x的当前存在个数；接着，借助分块思想，从逻辑上将0 ~ 1O^5 分为317块，其中每块的元素个数为316。可以定义一个统计数组block[317]，其中block[i]表示第i块中存在的元素个数。

如何查询序列中第K大的元素呢？首先，从小到大枚举块号，利用block数组累加得到前i-1块中存在的元素总个数，然后判断加入i号块的元素个数后元素总个数能否达到K。如果能，则说明第K大的数就在当前枚举的这个块中，此时只需从小到大遍历该块中的每个元素，利用table数组继续累加元素的存在个数，直到总累计数达到K，则说明找到第K大的数。

显然，整体思路先用O(N^(1/2))的时间复杂度找到第K大的元素在哪一块，然后再用O(N^(1/2))的时间复杂度在块内找到这个元素，因此单词查询的总时间复杂度为O(N^(1/2))。

是lowbit运算，即lowbit(x) = x & (-x)。

从二进制的角度，-x相当于把把x的二进制的每一位都取反，然后末位加1。而这等价于直接把x的二进制最右边的1左边的每一位都取反。

于是，可以推断出lowbit(x) = x & (-x)就是取x的二进制最右边的1和它右边所有0，因此它一定是2的幂次，及1，2，4，8等。

显然，lowbit(x)也可以理解为能整除x的最大2的幕次。

针对问题：给出一个整数序列A，元素个数为N(N≤10^5)，接下来查询K次(K≤10^5)，每次查询将给出一个正整数x(x≤N)，求前x个整数之和。

通常的做法是开一个sum数组，其中sum[i]表示前i个整数之和（数组下标从1开始），这样sum数组就可以在输入N个整数时就预处理出来。接着每次查询前x个整数之和时，输出sum[x]即可。显然每次查询的复杂度是O(1)，因此查询的总复杂度是0(K)。

升级问题：假设在查询的过程中可能随时给第x个整数加上一个整数v，要求在查询中能实时输出前x个整数之和。

树状数组(Binary Indexed Tree, BIT)。它其实仍然是一个数组，并且与sum数组类似，是一个用来记录和的数组，只不过它存放的不是前i个整数之和，而是在i号位之前（含i号位，下同）lowbit(i)个整数之和。