8月8号的树状数组：（位运算）

摘自：http://www.cnblogs.com/911/archive/2008/05/20/1203477.html

位运算是指按二进制进行的运算。在系统软件中，常常需要处理二进制位的问题。C语言提供了6个位操作

运算符。这些运算符只能用于整型操作数，即只能用于带符号或无符号的char,short,int与long类型。
C语言提供的位运算符列表：
运算符 含义 描述
& 按位与 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
| 按位或 两个相应的二进制位中只要有一个为1，该位的结果值为1（如果两个相应的二进制都为0，则该位的结果值为0，否则为1）
^ 按位异或 若参加运算的两个二进制位值相同则为0，否则为1
~ 取反 ~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1变0
<< 左移 用来将一个数的各二进制位全部左移N位，右补0
>> 右移 将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数，高位补0

下面的一系列介绍：现在还不常用。

常用的：

5、左移运算符（<<）
左移运算符是用来将一个数的各二进制位左移若干位，移动的位数由右操作数指定（右操作数必须是非负

值），其右边空出的位用0填补，高位左移溢出则舍弃该高位。
例如：将a的二进制数左移2位，右边空出的位补0，左边溢出的位舍弃。若a=15,即00001111（2），左移2

位得00111100（2）。
源代码：
#include <stdio.h>
main()
{
 int a=15;
 printf("%d",a<<2);
}
左移1位相当于该数乘以2，左移2位相当于该数乘以2*2＝4,15＜＜2=60，即乘了４。但此结论只适用于该

数左移时被溢出舍弃的高位中不包含1的情况。
    假设以一个字节（８位）存一个整数，若ａ为无符号整型变量，则ａ＝64时，左移一位时溢出的是0

，而左移2位时，溢出的高位中包含1。

6、右移运算符（>>）
右移运算符是用来将一个数的各二进制位右移若干位，移动的位数由右操作数指定（右操作数必须是非负

值），移到右端的低位被舍弃，对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分

用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。注

意：对无符号数,右移时左边高位移入0；对于有符号的值,如果原来符号位为0(该数为正),则左边也是移

入0。如果符号位原来为1(即负数),则左边移入0还是1,要取决于所用的计算机系统。有的系统移入0,有的

系统移入1。移入0的称为“逻辑移位”,即简单移位；移入1的称为“算术移位”。 
例： a的值是八进制数113755： 
   a:1001011111101101 （用二进制形式表示）
   a>>1: 0100101111110110 (逻辑右移时)
   a>>1: 1100101111110110 (算术右移时)
   在有些系统中,a>>1得八进制数045766,而在另一些系统上可能得到的是145766。Turbo C和其他一些C

编译采用的是算术右移,即对有符号数右移时,如果符号位原来为1，左面移入高位的是1。
源代码：
#include <stdio.h>
main()
{
 int a=0113755;
 printf("%d",a>>1);
}

突然发现前面写的一啪啦和树状数组没有半毛钱的关系！！！（其实呢，位运算是最原始，最省时间的运算吧）

接下来的是大BOSS：树状数组。

一开始我以为跟位运算有很大的关系呢。

大BOSS的起源：如果给定一个数组，要你求里面所有数的和，一般都会想到累加。但是当那个数组很大的时候，累加就显得太耗时了，时间复杂度为O(n)，并且采用累加的方法还有一个局限，那就是，当修改掉数组中的元素后，仍然要你求数组中某段元素的和，就显得麻烦了。所以我们就要用到树状数组，他的时间复杂度为O（lgn），相比之下就快得多。

大BOSS的长相：（这长相有科学依据的。）

其实这个图是想让我们发现：与其一个一个的求a数组，不如用个如c数组的树（肯定不是二叉树）

之后呢，你要求a数组的和时，就直接从树中找！并且这树有一特点：层层环扣：c1=a1，c2=a1+a2，c3=a3，c4=a1+a2+a3+a4，c5=a5，c6=a5+a6，c7=a7，c8=a1+a2+a3+a4+a5+a6+a7+a8，c9=a9，c10=a9+a10，c11=a11........c16=a1+a2+a3+a4+a5+.......+a16。

之后的一系列经过复杂的计算，简单的证明，就与位运算挂钩了。

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

这个是树状数组的核心：由它的存在建立如图c数组的树。

我一直忽略的是：这种树的结构让查找不用接触本体，直接找“根节点”就行了。（好像一般树都有此功能才会节省时间的，为什么我只会看到表面的东西。老了，只能看到肤浅，不能渗透本质啊！难怪追不到女生。。。（女人心，海底针））

那么之后的代码就好理解了。（上面的只是一时兴起所为，看不懂很正常）

吐槽一下：为什么算法中最难的，扯的最远的，最抽象的就是树！而火影中最强的初代火影（柱间，为什么要个木字旁呢？还不如叫个“树间”得了）也是会召唤出几棵树来折腾人，并且全篇不停的灌输这棵“树”的强大。我擦可能这日货也是早年深受ACM的毒害吧。（纯属胡扯）

具体参见：http://www.cnblogs.com/zhangshu/archive/2011/08/16/2141396.html

接下来进入实战阶段：

最简单的：HDU 1541和HDU 1556开始

一个是更新点，求区间和。一个是更新区间，求点值。（反正时刻明确此树状数组的特性和长相）

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int tree[100005];
void update(int x,int n)
{
    while(x<=100005)
    {
        tree[x]+=n;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=x&(-x);
    }
    return sum;
}
int main()
{
    int n,i,a1,a2;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        if(n==0)
            break;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a1,&a2);
            update(a1,1);
            update(a2+1,-1);
        }
        for(i=1;i<=n;i++)
        {
            if(i<n)
                printf("%d ",sum(i));
            else
                printf("%d
",sum(n));
        }
    }
    return 0;
}

时刻谨记BOSS的长相，技能，血量。以便能在不掉血的情况下，更快秒掉他！

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int tree[35005];
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=x&(-x);
    }
    return sum;
}
void update(int x)
{
    while(x<=35000)
    {
        tree[x]++;
        x+=x&(-x);
    }
}
int main()
{
    int n,i,a1,a2,level[35005];
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        memset(level,0,sizeof(level));
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a1,&a2);
            level[sum(a1+1)]++;//坐标从零开始的，而此树从1开始的
            update(a1+1);
        }
        for(i=0;i<n;i++)
            printf("%d
",level[i]);
    }
    return 0;
}

Ultra-QuickSort　POJ 2299

这个题就是求逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。（逆序数的个数如冒泡法排序进行的次数！）

俩种方法：归并排序和离散化＋树状数组

先说下离散化：

我只知道这个题目离散化主要用来：因为数的范围是999999999。而最多500000个数，所以数和数之间的间隔很大，可以处理一下，使数的间隔变小！

如一列数：１,９９,１００００,３４　离散化后：１,３,４,２

那么看代码：

 如果数据的范围是999999999（没有这么大），那么可以直接用现状数组了吧。。。（个人猜测）

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int a1[500005],tree[500005];         //排序后从新编号用的
int n;
struct line
{
    int x;
    int y;
}a[500005];
bool comp1(line i,line j)
{
    return i.x<j.x;
}
void update(int x)
{
    while(x<=n)
    {
        tree[x]++;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=x&(-x);
    }
    return sum;
}
int main()
{
    int i;
    __int64 s;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        s=0;
        if(n==0)
            break;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].y=i;
        }
        sort(a+1,a+1+n,comp1);
        a1[a[1].y]=1;
        for(i=2;i<=n;i++)
        {
            if(a[i].x!=a[i-1].x)
                a1[a[i].y]=i;
            else
                a1[a[i].y]=a1[a[i-1].y];
        }
        for(i=1;i<=n;i++)
        {
            update(a1[i]);
            s+=(sum(n)-sum(a1[i]));              //每次累加该数前面比他大的数的个数
        }
        printf("%I64d
",s);
    }
    return 0;
}

还有归并排序：（先缓一下）

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <algorithm>
#define MAX 500010
using namespace std;
int a[MAX];
int tb[MAX/2],te[MAX/2];
long long sum;
void Merger(int *a,int beg,int mid,int end)
{
    int k;
    int n1 = mid - beg + 1;
    int n2 = end - mid;
    int i = 0,j = 0;
    for(k=beg; k<=mid; k++)
        tb[i++] = a[k];
    tb[n1] = INT_MAX;

    for(k=mid+1; k<=end; k++)
        te[j++] = a[k];
    te[n2] = INT_MAX;

    i = j = 0;

    for(k=beg; k<=end; k++)
        if( tb[i] <= te[j] )
            a[k] = tb[i++];
        else
        {
            sum += ( n1 - i );
            a[k] = te[j++];
        }
}
void Mergersort(int *a,int beg,int end)
{
    if( beg < end )
    {
        int mid = (beg+end)/2;
        Mergersort(a,beg,mid);
        Mergersort(a,mid+1,end);
        Merger(a,beg,mid,end);
    }
}
int main()
{
    int n,i;
    while( ~scanf("%d",&n) && n )
    {
        sum = 0;
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        Mergersort(a,0,n-1);
        printf("%lld
",sum);
    }
return 0;
}