树状数组

一个基本的问题：求数组中的逆序对数目?

这也是算法导论第一章的最后一道习题。按照算法导论中的提示，该问题可以通过修改合并排序在O(nlgn)内解决。另外一种方法，是使用一种特殊的数据结构称之为“树状数组”，也可以在O(nlgn）内解决。代码如下：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define MAXN 100002
#define MAX 1000002
int n,a[MAXN],c[MAX] ;
int main()
{
 int runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
  long long ret = 1LL * n * (n - 1) / 2 ;
  memset(c,0,sizeof c) ;
  for(int i = 0;i < n;i++)
  {
   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;  
  }
  cout << ret << endl ;
 }
 return 0 ;
}

下面介绍下树状数组（Binary Indexed Tree)。如果搜一下，就会发现有很多文章详细介绍树状数组,比如这篇,所以这里不再赘述。 它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题：数组{a}中的元素可能不断地被修改，怎样才能快速地获取连续几个数的和？ 传统数组(共n个元素)的元素修改和连续元素求和的复杂度分别为O(1)和O(n)。树状数组通过将线性结构转换成伪树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)，大大提高了整体效率。 let the code talk.值得提一下的是，树状数组下标是从1开始的。

//求2^k
int lowbit(int t)
{
    return t & ( t ^ ( t - 1 ) );
}
 
//求前n项和
int sum(int end)
{
   int sum = 0;
   while(end > 0)
  {
     sum += in[end];
     end -= lowbit(end);
  }
 
  return sum;
}
 
//增加某个元素的大小
void plus(int pos, int num)
{
   while(pos <= n)
  {
     in[pos] += num;
     pos += lowbit(pos);
  }
}