一維樹狀數(shù)組
#define lowbit(x)  ( (x)&(-(x)) )

void  update( int pos, int value )      // 更新 pos 的值
{
    int x= pos;
    while( x<= n )
    {
        count[x]+= value;
        x+= lowbit(x);
    }
}

int  getsum( int pos )                  //  求 1 到 pos 位置的和
{
    int x= pos, sum= 0;
    while( x )
    {
        sum+= count[x];
        x-= lowbit(x);
    }
    
    return sum;
}

相關(guān)習(xí)題： http://acm.pku.edu.cn/JudgeOnline/problem?id=2352

樹狀數(shù)組可以用來求逆序數(shù)， 當(dāng)然一般用歸并求。
如果數(shù)據(jù)不是很大， 可以一個個插入到樹狀數(shù)組中， 每插入一個數(shù)， 統(tǒng)計
比他小的數(shù)的個數(shù)，對應(yīng)的逆序為 i- getsum( data[i] ),其中 i 為當(dāng)前已
經(jīng)插入的數(shù)的個數(shù)， getsum( data[i] ）為比 data[i] 小的數(shù)的個數(shù)
i- sum( data[i] ) 即比 data[i] 大的個數(shù)， 即逆序的個數(shù)
但如果數(shù)據(jù)比較大，就必須采用離散化方法。

一關(guān)鍵字的離散化方法：

所謂離散化也就是建立一個一對一的映射。 因為求逆序時只須要求數(shù)據(jù)的相應(yīng)
大小關(guān)系不變。
如： 10 30 20 40 50  與  1 3 2 4 5 的逆序數(shù)是相同的

定義一個結(jié)構(gòu)體  struct Node{ int data;    // 對應(yīng)數(shù)據(jù)
                                                   int pos;     // 數(shù)據(jù)的輸入順序 };
先對 data 升序排序， 排序后，pos 值對應(yīng)于排序前 data 在數(shù)組中的位置。
再定義一個數(shù)組 p[N]， 這個數(shù)組為原數(shù)組的映射。以下語句將按大小關(guān)系
把原數(shù)組與 1到 N 建立一一映射。

int id= 1; p[ d[1].pos ]= 1;
for( int i= 2; i<= n; ++i )
if( d[i].data== d[i-1].data ) p[ d[i].pos ]= id;
else                                    p[ d[i].pos ]= ++id;

相關(guān)習(xí)題：http://acm.pku.edu.cn/JudgeOnline/problem?id=2299

poj 2298
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 500010 
#define lowbit(x)  ( (x)&(-(x)) )

struct Node{ int data, pos; };

int n;
int count[N], p[N];
Node d[N];

int cmp( const void* a, const void* b )
{
    Node* ta= (Node*)a;
    Node* tb= (Node*)b;
    
    return ta->data- tb->data;
}

void  update( int pos, int value )
{
    int x= pos;
    while( x<= n )
    {
        count[x]+= value;
        x+= lowbit(x);
    }
}

int  getsum( int pos )
{
    int x= pos, sum= 0;
    while( x )
    {
        sum+= count[x];
        x-= lowbit(x);
    }
    
    return sum;
}

int main()
{
    while( scanf("%d",&n)!= EOF )
    {
        if( n== 0 ) break;
        
        for( int i= 1; i<= n; ++i )
        {
            scanf("%d", &d[i].data );
            d[i].pos= i; 
        }
            
        qsort( d+ 1, n, sizeof(d[0]), cmp );
        
        int id= 1; p[ d[1].pos ]= 1;

        for( int i= 2; i<= n; ++i )
        if( d[i].data== d[i-1].data ) p[ d[i].pos ]= id;
        else                          p[ d[i].pos ]= ++id;
        
        memset( count, 0, sizeof(count) );
        
        __int64 ans= 0;
        for( int i= 1; i<= n; ++i )
        {    
            update( p[i], 1 );
            ans+= (__int64)( i- getsum( p[i] ) );            
        }
        
        printf("%I64d\n", ans );
    }
    
    return 0;
}

二關(guān)健字的離散方法：

先對第一個關(guān)鍵字進(jìn)行離散化，然后對第二關(guān)鍵字排序。

相關(guān)習(xí)題：
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10069&courseid=0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX  100001
#define lowbit(x)  ( (x)&( (x)^( (x)- 1 ) ) )

struct Point
{
    int x, y, id, xid;
};

int    n;
Point  pos[MAX];
int    count[MAX];
int    result[MAX];

int cmpa( const void* a, const void* b )
{
    Point*  ta= (Point*)a;
    Point*  tb= (Point*)b;
    
    if( ta->x== tb->x ) return tb->y- ta->x;
    
    return ta->x- tb->x;
}

int cmpb( const void* a, const void* b )
{
    Point* ta= (Point*)a;
    Point* tb= (Point*)b;
    
    if( ta->y== tb->y ) return ta->x- tb->x;
    
    return tb->y- ta->y;
}

void add( int i )
{
    while( i<= MAX )
    {
        count[i]++;
        i+= lowbit(i);
    }
}

int sum( int i )
{
    int total= 0;
    while( i>= 1 )
    {
        total+= count[i];
        i-= lowbit(i);
    }
    return total;
}

int main()
{
    while( scanf("%d", &n)!= EOF )
    {
        memset( count, 0, sizeof(count) );
        memset( result, 0, sizeof(result) );
        
        for( int i= 0; i< n; ++i )
        {
            scanf("%d%d", &pos[i].x, &pos[i].y );
            pos[i].id= i;
        }
        
        qsort( pos, n, sizeof(pos[0]), cmpa );
        
        int tx= pos[0].x,t= 1;
        for( int i= 0; i< n; ++i )
        {
            if( pos[i].x== tx  )
                pos[i].xid= t;
            else
            {
                pos[i].xid= ++t;
                
                tx= pos[i].x;
            }
        }
        qsort( pos, n, sizeof(pos[0]), cmpb );
        
        for( int i= 0; i< n; ++i )
         {
            result[ pos[i].id ]= sum( pos[i].xid );    
            
            if( i> 0 && pos[i].x== pos[i-1].x && pos[i].y== pos[i-1].y ) 
                     result[ pos[i].id ]= result[ pos[i-1].id ];
                     
            add( pos[i].xid );
        }
            
        for( int i= 0; i< n; ++i )
        {
            if( i== 0 )  printf("%d", result[i] );
            else         printf(" %d", result[i] );
        }
        printf("\n");
    }
    
    return 0;
}

二維樹狀數(shù)組

基本構(gòu)造：

#define MAXN 1025

int count[MAXN][MAXN];
int n;

int lowbit( int x ){ return x&(-x); }

void update( int x, int y, int value ){
    int i= x, j= y;
    while( i<= n ){
        j= y;
        while( j<= n ){
            count[i][j]+= value;
            j+= lowbit(j);
        }    
        i+= lowbit(i);
    }
}

// 計算 ( 1, 1 )到 ( x, y )區(qū)域的和 
int getsum( int x, int y ) 
{
    int i= x, j= y, sum= 0;
    
    while(i){
        j= y;
        while(j){        
            sum+= count[i][j];
            j-= lowbit(j);
        }
        i-= lowbit(i);
    }
    return sum;
}

// x2> x1 && y2> y1 (x1,y1)到(x2,y2)和 
int total( int x1, int y1, int x2, int y2 ) 
{
    return getsum( x2, y2 )- getsum( x2, y1- 1 )
        - getsum( x1- 1, y2 )+ getsum( x1- 1, y1- 1 ); 
}

相關(guān)習(xí)題： http://acm.pku.edu.cn/JudgeOnline/problem?id=3321