树状数组――poj 3928

树状数组是一个思想很巧妙的算法。

树状数组主要是求动态连续和、查询等问题

先理解lowbit(i) ， i是指数组中的位置（从1开始） ， lowbit(i) 是i的二进制表达式中最右边的1所对应的值 ， 也就是说lowbit(i) = i&(-i)

假设a[i]存储的是树 ， c[i]是表示a[i] + a[i-1].......+a[i-lowbit(i)] ， 那么这时 ， 我们要求数组a中前 i 个数和 （a[i]+a[i-1].....+a[1]），我们只需要这么求：

int sum_tree_shuzu(int i)
{
    int sum = 0;
    while(i>0)
    {
        sum += c[i];
        i -= lowbit(i);
    }
    return sum;
}

当我们改变了数组a中的某个数时 ， 应该怎么来改变数组c中的值呢。

我们假设改变：a[i] = a[i]+d；

这时我们只需要改变数组 c 中和 a[i] 相关的值。

void add_tree_shuzu(int i , int d)
{
    while(i <= n)
    {
        b[i] += d;
        i += lowbit(i);
    }
}

下面说一下例题：poj 3928

这个题目的关键点：

1、每个队员的能力值都不一样 ， 就说没有想等的能力值

2、我们只需要对裁判遍历。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int a[20010] , b[20010] , c[20010]; int n; bool cmp(int i , int j) { return a[i] <= a[j]; } inline int lowbit(int y) { return y&(-y); } int sum_tree_shuzu(int y) { int sum = 0; while(y>0) { sum += b[y]; y -= lowbit(y); } return sum; } void add_tree_shuzu(int i , int x) { while(i <= n) { b[i] += x; i += lowbit(i); } } int main() { int t; scanf("%d" , &t); while(t--) { scanf("%d" , &n); int i , x , j; memset(b , 0 , sizeof(b)); for(i = 1; i <= n; i++) { scanf("%d" , &a[i]); c[i] = i; } sort(c+1 , c+n+1, cmp); //对队员的能力值进行排序， add_tree_shuzu(c[1] , 1); __int64 sum = 0; for(i = 2; i < n; i++) { x = sum_tree_shuzu(c[i]); sum += x*(n-c[i]-i+x+1) + (i-1-x)*(c[i]-1-x);//裁判住在c[i]的位置，那么有i-1个队员住在裁判前面，n-i个队员住在裁判后面 add_tree_shuzu(c[i] , 1); } printf("%I64d\n" , sum); } return 0; }