树状数组
树状数组具体的定义：查看百度百科
树状数组的模拟理解可以是这样的，对于树状数组而言你完全可以把它看做是一个辅助的数组。至于它是什么样的辅助数组就和定义有关了。首先，你有一个数组A[100]里面存放着相应的数据，而这时又定义了一个辅助数组C[100]，C[100]的作用就是记录A数组中某几个元素的和。而对于树状数组，我们规定C[1]存的是A[1],C[2]存的是A[1]+A[2]…如下图：
既然我们已经知道C数组仅仅是起到辅助作用，那么我们在思考的时候完全不必想其构造过程，只需要懂得构造方法和C数组究竟代表什么即可。
对于树状数组的算法一般都会有看到一个函数是：lowbit()函数，可以查看博客探究它的含义。现在只需要知道它是用来构造辅助数组C的就可以了。
int lowbit(int x)
{
return x&(-x);
}
紧接着会是这样两个函数：
int sum(int x)
{
int result=0;
while(x>0)
{
result+=c[x];
x-=lowbit(x);
}
return result;
}
void add(int x,int n)
{
while(x<MAX)
{
c[x]+=n;
x+=lowbit(x);
}
}
在这里你需要明确的就是这两个函数都和辅助数组C有关，但是实质是获取A的信息（因为C是辅助数组，用在存A中的信息的）。第一个函数是表示获取数组A[1]到A[x]的和。
第二个函数则是在A数组中的第x位置上加上个数n。而我们在程序使用中并没有定义数组A（没必要浪费空间）原因是我们所有的操作都是在C（可以想象存在一个A，然后C它的辅助数组）上进行的，通过C来获取信息。
这样基本上就算对树状数组有所了解了。有些人肯定会很疑问，不明白如果没有定义A如何构造C呢？其实这就归结于第二个函数add() 我们可以利用add()去构造C.
例如：
有一串数据 1 2 3 4
我们想把他们存到A中(A[1]=1,A[2]=2,A[3]=3,A[4]=4)这里面没有用A[0]是因为lowbit()函数，所以树状数组使用应注意不能用0号空间。
这时我们只需要
for(i=1;i<=n;i++)
{
int temp=0;
cin>>temp;
add(i,temp);
}
可以理解为每次输入一个值，我就把它存到数组A的对应空间中，而数组A并不是真实存在的。但是数组C存在且add是针对数组C进行操作的。这样就利用了add构造了虚拟的数组A同时也构造了相应的辅助数组C。
而我们想获得A数组前N项和的时候只需要sum(N)即可。（一定要理解好A和C的关系）
树状数组使用变型1：
上面已经介绍了关于构造数组C的函数，接下来就对同一个函数进行用法上的改变。
对于add函数来说：
for(i=1;i<=n;i++)
{
int temp=0;
cin>>temp;
add(temp,1);
}
这样的写法会令初学者困扰，而仔细看就很容易发现。其实就是输入一个数我们就以这个数为索引即：A[temp]，让它的值为1。说白了就是把A数组用来计数，输入1我就在1号空间把其值变成1,输入1000就在1000号空间变1。而C数组的本质还没有改变，仍然指的是A某几个单元的和。仍然是辅助数组。
树状数组使用变型2：
第二种变型是涉及到两个函数add和sum的，这时你就需要去了解下add和sum函数的内部结构，和C数组的构造过程了，而不能单单关注他们的含义了。含义只是使其思考及其使用上更加方便，但实质还需要了解的。
下面给出两个函数的变型：
int sum(int index)
{
int result=0;
while(index<MAX)//注意此处不同
{
result+=c[index];
index+=lowbit(index); //注意此处不同
}
return result;
}
void add(int index, int number)
{
while(index>0) //注意此处不同
{
c[index]+=number;
index-=lowbit(index); //注意此处不同
}
}
如果两个函数进行了如上的更改，则其含义已然改变。此时add指的是将数组A的前N项都加上number。即：add(n,number);
如：add(3,1)就是指将A数组的前三个空间都加1；
则此时的C也并不代表是A的某几项元素之和了！因为他的构造的函数add已经发生了改变，这时C存的就是对应A的值。而sum函数就是返回当前索引下A数组中的值（也就是C数组中的值）
如：C[3]=A[3]=1;则sum(3)的值就是1
离散化
对于数组变型1而言，我们曾用数组进行计数，输入100则就令A[100]=1。然而当我们输入的数比较大例如1000000000,那我们就没必要开那么大的数组了。例如如下一串数：
1000 999 998
我们想求998之前比998大的数，也就是998的逆序数。那么我们没必要开1000的数组去存三个数，而是将其进行离散化为 3 2 1即可。这样一来他们之间的大小关系和前后顺序没有受到任何影响，同时只需要开3个空间大小的数组即可。
思路很简单，具体代码如下：
struct data
{
int index;//输入的顺序的索引 第几个输入的就是几
int value;//输入的值
}a[MAX];
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].value);//获得值
a[i].index=i;//获得索引
}
sort(a+1,a+n+1,cmpv);//利用值进行排序，显然先后顺序乱了
for(i=1;i<=n;i++)//利用索引将其离散化，并还原成原来的输入顺序
{
b[a[i].index]=i;
}