题目：http://acm.hdu.edu.cn/showproblem.php?pid=2852
题意：三种操作：
0 插入
1 删除
2 查找比a大的第k个数。
思路：看了大神都是用树状数组写的，自己也便去学了树状数组
什么是树状数组?
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
树状数组十分容易实现，代码量小，时间复杂度低，并且经过数学处理后也可以实现成段更新。线段树也可以做到和树状数组一样的效果，但是代码要复杂得多。不过要注意，一般情况下树状数组能解决的问题线段树都能解决，反之有些线段树能解决的问题树状数组却不行。
令这棵树的结点编号为C1，C2…Cn。令每个结点的值为这棵树的值的总和，那么容易发现
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
如果要求 a[1] ~ a[7] 的和，即为 C[7] + C[6] + C[4] ，如果要改变 a[1] 的值，改变C数组中和 a[1] 有关的项即可（即 C[1] C[2]C[4] C[8]）。 这就是树状数组！实现了O(logn)的查询和删改。
这里有一个有趣的性质：设节点编号为x，那么这个节点管辖的区间为 2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，所以很明显：Cn = A(n – 2^k + 1) + … + An，算这个2^k有一个快捷的办法，定义一个函数如下即可（求解2^k即求二进制码右边第一位1的值）：
int lowbit(int x) {
return x & (-x);
}
当想要查询一个SUM(n)(求a[1]~a[n]的和），可以依据如下算法即可：
令sum = 0，转第二步；
假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；
令n = n – lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。所以修改算法如下（给某个结点i加上x）：
当i > n时，算法结束，否则转第二步；
Ci = Ci + x， i = i + lowbit(i)转第一步。i = i + lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。 对于数组求和来说树状数组简直太快了!
树状数组基本模板：
#include <stdio.h>
#define N 100
int a[N];//原数组,从1开始
int c[N];//树状数组,从1开始
int n;//数组的实际数据的大小
int lowbit(int i) //取右边第一次出现1的位数，如10100,则取100, 11则取1
{
//原理：拿一个正数来说，它对应的负数在计算机中用补码表示方式为：从低位到高位，第一个出现1以后，0变1,1变0.
// 那么这个数和它的负数在计算机中的表示正好从低位到高位第一个1出现之前，都是一样的，之后每一位正好想法，&
//操作后，正好取到了要取的那几位
return i&(-i);
}
void modify(int pos, int num) //a是原数组，当a[pos]增加num时，树状数组相应的变化
{
while (pos <= n) {
c[pos] += num;
pos += lowbit(pos);
}
}
void getResult(int pos) //计算a[1]-a[pos]的和
{
//比如计算a[1]~a[6]的和，首先c[6]肯定是xx到a[6]的和，6是0110, lowbit是10, 所以c[6]对应的是0101～0110
//的和，即a[6]+a[5]计算了后两位，还剩下0110－10(pos－lowbit(pos)), 下面要算0100, a[1]~a[4]的和c[4]肯
//定是xx到a[4]的和，0100的lowbit是100, 所以c[4]对应的是0001～0100的和，即a[1]+..+a[4]a[1]~a[6]的和已
//经全部算出了
int sum = 0;
while (pos ) {
sum += c[pos];
pos -= lowbit(pos);
}
return sum;
}
void init()//初始化树状数组
{
int i;
scanf("%d", &n);
for (i=1; i<=n; i++)
{
scanf("%d", &a[i]);
modify(i, a[i])
}
}
本题中0 1 操作都好进行，我们令数组a 下角标为数据的值，初始化都为0，插入a的值为1，删除a为-1，.所以0<角标<100000,进行操作2时，就是查找a到100000中有没有值大于等于sum(a)+k,d的数组的角标存在。对于数据大，有序排列的数，可以用二分法查找。
#include <stdio.h>
#include <string.h>
int C[100005];
int lowbit(int k)
{
return k & (-k);
}
int sum(int x)
{
int ans = 0;
while (x > 0)
{
ans += C[x];
x -= lowbit(x);
}
return ans;
}
void add(int nn, int val)
{
while (nn <= 100000)
{
C[nn] += val;
nn += lowbit(nn);
}
}
void search(int a, int k)//金典 二分法
{
int L = a, r = 100000, mi;
int now = sum(a);
while (L < r)
{
int mid = (L+r)/2;
mi = sum(mid);
if (mi < now + k)
L = mid + 1;
else
r = mid;
}
if (sum(L)>= now + k)
printf("%d\n", L);
else
printf("Not Find!\n");
}
int main()
{
int n;
while (scanf("%d", &n)!=EOF)
{
memset(C, 0, sizeof C);
int p, aa, kk;
while (n--)
{
scanf("%d%d", &p, &aa);
if (p == 0)
{
add(aa, 1);
}
else if (p == 1)
{
if (sum(aa) - sum(aa-1) == 0)
printf("No Elment!\n");
else add(aa, -1);
}
else
{
scanf("%d", &kk);
search(aa, kk);
}
}
}
}