树状数组的区间求和单点更新只与操作数组c[] 相关 ; 与a[] 并无关系;

int lowbit(int x){    return x & (-x);}void modify(int x,int add)  //一维(修改) ; {      while(x<=MAXN)      {              a[x]+=add;            x+=lowbit(x);     }}int get_sum(int x)      //求和 {      int ret=0;     while(x!=0)      {               ret+=a[x];           x-=lowbit(x);       }      return ret;}void modify(int x,int y,int data)//二维(修改){    for(int i=x;i
     
      0;i-=lowbit(i))        for(int j=y;j>0;j-=lowbit(j))            res+=a[i][j];    return res;}int main(){    //1D;     {        int a, b;        printf("%d%d", &a, &b);        modefy(a, b);        sum=get_sum(b, a-1);        }    //2D;    {        int x, x1, y, y1;        scanf("%d%d%d%d", &x, &x1, &y, &y1);        if(x>x1) swap(x, x1);        if(y>y1) swap(y, y1);        int rec=get_sum(x1, y1)-get_sum(x-1, y1)-get_sum(x1, y-1)+get_sum(x-1, y-1);    }    return 0;    }
     

 

 

hdoj2642--Stars

//注意数组脚标从1开始#include 
     
      #include 
      
       #include 
       
        #define MAXN 1001using namespace std;int n, a[MAXN][MAXN]; bool b[MAXN][MAXN];int lowbit(int x){    return x &(-x);}void modify(int x, int y, int data){    for(int i=x; i<=MAXN; i+= lowbit(i))        for(int j=y; j<=MAXN; j+= lowbit(j))            a[i][j] += data;            } int getSum(int x, int y){    int res=0;    for(int i=x; i>0; i -= lowbit(i))        for(int j=y; j>0; j-= lowbit(j))            res +=a[i][j];    return res;}int main(){    scanf("%d", &n);     memset(b, 0, sizeof(b));    while(n--)    {        int x, x1, y1, y;         char str[2]; scanf("%s", str);        if(str[0]=='B')        {            scanf("%d%d", &x, &y);            x++; y++;            if(b[x][y]) continue;            modify(x, y, 1);            b[x][y]=1;         }        else if(str[0]=='D')        {            scanf("%d%d", &x, &y);            x++; y++;            if(!b[x][y]) continue;            modify(x, y, -1);            b[x][y]=0;        }        else        {            scanf("%d%d%d%d", &x, &x1, &y, &y1);            x++; y++; x1++; y1++;            if(x>x1) swap(x, x1);            if(y>y1) swap(y, y1);            int rec=getSum(x1, y1)-getSum(x-1, y1)-getSum(x1, y-1)+getSum(x-1, y-1);            printf("%d\n", rec);        }            }    return 0;}
       
      
     

hdoj1394求逆序数：

逆序对性质: 交换两个相邻数,逆序数+1或-1, 交换两个不相邻数a, b, 逆序数+=两者间大于a的个数-两者间小于a的个数

可得公式: ans= ans+n-a[i]-(a[i]-1);

#include 
     
      #include 
      
       const int MAXN = 5050;using namespace std;int a[MAXN], c[MAXN];int n;int lowbit(int x){    return x&(-x);}void add(int i, int val){    while(i <=n)    {        c[i] += val;        i +=lowbit(i);    }}int sum(int i){    int s=0;    while(i>0)    {        s+=c[i];        i-= lowbit(i);    }    return s;}int main(){    while(scanf("%d", &n) != EOF)    {        int ans=0;        memset(c, 0, sizeof(c));        for(int i=1; i<=n; i++)        {            scanf("%d", &a[i]);            a[i]++;            ans += sum(n)-sum(a[i]);            add(a[i], 1);        }        int Min=ans;        for(int i=1; i<=n; i++)        {            ans += n-a[i]-(a[i]-1);            if(ans