一维树状数组基本构造:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
一维树状数组
#define lowbit(x) ( (x)&(-(x)) )
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void update( int pos, int value ) // 更新 pos 的值
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x= pos;
while( x<= n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
count[x]+= value;
x+= lowbit(x);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int getsum( int pos ) // 求 1 到 pos 位置的和
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x= pos, sum= 0;
while( x )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum+= count[x];
x-= lowbit(x);
}
return sum;
}
相关习题: http://acm.pku.edu.cn/JudgeOnline/problem?id=2352
树状数组可以用来求逆序数, 当然一般用归并求。
如果数据不是很大, 可以一个个插入到树状数组中, 每插入一个数, 统计
比他小的数的个数,对应的逆序为 i- getsum( data[i] ),其中 i 为当前已
经插入的数的个数, getsum( data[i] )为比 data[i] 小的数的个数
i- sum( data[i] ) 即比 data[i] 大的个数, 即逆序的个数
但如果数据比较大,就必须采用离散化方法。
一关键字的离散化方法:
所谓离散化也就是建立一个一对一的映射。 因为求逆序时只须要求数据的相应
大小关系不变。
如: 10 30 20 40 50 与 1 3 2 4 5 的逆序数是相同的
定义一个结构体 struct Node{ int data; // 对应数据
int pos; // 数据的输入顺序 };
先对 data 升序排序, 排序后,pos 值对应于排序前 data 在数组中的位置。
再定义一个数组 p[N], 这个数组为原数组的映射。以下语句将按大小关系
把原数组与 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;
相关习题:http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
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;
}
二关健字的离散方法:
先对第一个关键字进行离散化,然后对第二关键字排序。
相关习题:
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10069&courseid=0
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define MAX 100001
#define lowbit(x) ( (x)&( (x)^( (x)- 1 ) ) )
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct Point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x, y, id, xid;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
Point pos[MAX];
int count[MAX];
int result[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmpa( const void* a, const void* b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
Point* ta= (Point*)a;
Point* tb= (Point*)b;
if( ta->x== tb->x ) return tb->y- ta->x;
return ta->x- tb->x;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmpb( const void* a, const void* b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
Point* ta= (Point*)a;
Point* tb= (Point*)b;
if( ta->y== tb->y ) return ta->x- tb->x;
return tb->y- ta->y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add( int i )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while( i<= MAX )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
count[i]++;
i+= lowbit(i);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int sum( int i )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int total= 0;
while( i>= 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
total+= count[i];
i-= lowbit(i);
}
return total;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while( scanf("%d", &n)!= EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset( count, 0, sizeof(count) );
memset( result, 0, sizeof(result) );
for( int i= 0; i< n; ++i )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if( pos[i].x== tx )
pos[i].xid= t;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
pos[i].xid= ++t;
tx= pos[i].x;
}
}
qsort( pos, n, sizeof(pos[0]), cmpb );
for( int i= 0; i< n; ++i )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if( i== 0 ) printf("%d", result[i] );
else printf(" %d", result[i] );
}
printf("\n");
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
二维树状数组
基本构造:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
#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 )区域的和
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 );
}
相关习题: http://acm.pku.edu.cn/JudgeOnline/problem?id=3321
posted on 2009-04-10 15:01
Darren 阅读(482)
评论(1) 编辑 收藏 引用