树状数组的应用
1、单点更新，区间求值。（HDU1166）
2、区间更新，单点求值。（HDU1556）
3、二维树状数组 (poj1195)
4、求逆序对。（HDU2838）
5、求逆序数。（HDU2689）
对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个
不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序对。一个排列中所有逆序对总数叫做这个排列的逆序数。
例如：标准为次序为1
2 3 4，则4 3 2 1，的逆序数为6，逆序对为(4,3) (4,2) (4,1) (3,2) (3,1) (2,1)；
树状数组如下图所示：
c1=a1 c3=a3 c5=a5 c7=a7 c9=a9
c2=a1+a2 c4=a1+a2+a3+a4 c6=a5+a6 c8=a1+a2+a3+a4+a5+a6+a7+a8 c10=a9+a10
c11=a11........c16=a1+a2+a3+a4+a5+.......+a16
分析上面的几组式子可知，当 i 为奇数时，ci=ai ；当 i 为偶数时，就要看 i 的因子中最多有二的多少次幂，例如，6 的因子中有 2 的一次幂，等于 2 ，所以 c6=a5+a6（由六向前数两个数的和），4 的因子中有 2 的两次幂，等于 4 ，所以 c4=a1+a2+a3+a4（由四向前数四个数的和）。
这段代码理解为树状数组向前，或者向后衍生用的
int lowbit(int n)
{
return n&(-n);
}
这段代码用来更新树状数组用的
void Add(int n, int v)
{
while (n>0)
{
Tree[n] += v;
n -= lowbit(n);
}
}
这段代码用来求树状数组前缀和的
int get(int n)
{
int sum = 0;
while (n<=num)
{
sum += Tree[n];
n += lowbit(n);
}
return sum;
}
hdu1556
#include <iostream>
using namespace std;
#define MAX 100001
int Tree[MAX];
int a, b, num;
int lowbit(int n)
{
return n&(-n);
}
void Add(int n, int v)
{
while (n>0)
{
Tree[n] += v;
n -= lowbit(n);
}
}
int get(int n)
{
int sum = 0;
while (n<=num)
{
sum += Tree[n];
n += lowbit(n);
}
return sum;
}
int main()
{
int i;
while (scanf("%d", &num)!=EOF && num)
{
memset(Tree, 0, sizeof(Tree));
for (i=1; i<=num; i++)
{
scanf("%d%d",&a, &b);
Add(b, 1);
Add(a-1, -1);
}
for (i=1; i<num; i++)
printf("%d ", get(i));
printf("%d\n", get(num));
}
return 0;
}