nyoj 树状数组系列

客官°小女子只卖身不卖艺 2022-03-20 08:42 131阅读 0赞

树状数组之插线问点题：

http://acm.nyist.net/JudgeOnline/problem.php?pid=123

树状数组之插点问线题：

http://acm.nyist.net/JudgeOnline/problem.php?pid=116

树状数组之求逆序数

[http://acm.nyist.net/JudgeOnline/problem.php?pid=117][http_acm.nyist.net_JudgeOnline_problem.php_pid_117]

![Image 1][]

![2010102420055023.png][]

树状数组是一个很特殊的数据结构，如右图所示，其特殊性也决定其相比较普通数组来说有了log(n)的复杂度，因此用途比较大。

树状数组一般有两种操作，插点问线和插线问点。先说插线问点，就如上面的题目123，让某个区间上的每个元素进行更新，多个区间更新后，最后问某个节点的元素或值是多少，若使用普通数组来处理的话，每次更新区间就是循环区间的每个元素进行更新，其时间复杂度就在更新上，为O(n)。 若是用树状数组的话，若是更新区间(a,b)上的值，我们只需要让b之前的每个元素都加上更新值count，让a以前的元素都加上 -count，这其实是插点问线中的求和操作。然后询问节点元素时，我们也是求造成影响的所有区间的和，考虑每次更新都是向前更新，也就是说，若一个区间对某个节点造成影响，则该区间一定有端点在该点的右面，因此我们查询时向后更新。

下面来看看上面123题的代码：

#include <cstdio>
    #include <cstring>
    int soldier[1000010];
    int t,st,end,m,count,n;
    int lowbit(int x)  
    {
        return x&(-x);
    }
    void update(int n,int count)  //向前更新
    {
        while(n>0)
        {
            soldier[n]+=count;
            n-=(lowbit(n));
        }
    }
    int sum(int n)  //向后求和
    {
        int sum=0;
        while(n<=m)
        {
            sum+=soldier[n];
            n+=lowbit(n);
        }
        return sum;
    }
    int main()
    {
        int T, i, j, first, end, score, res;
        char str[10];
        scanf("%d%d", &T, &m);
        memset(soldier, 0, sizeof(soldier));
        while(T--)
        {
            scanf("%s", str);
            if(strcmp(str, "ADD") == 0)
            {
                scanf("%d%d%d", &first, &end, &score);
                update(first - 1, -score);
                update(end, score);
            }
            else
            {
                scanf("%d", &res);
                printf("%d\n", sum(res));
            }
        }
        return 0;
    }

其中lowbit(n)函数是树状数组最巧妙的一点，不知道其意思的可以自己写一个程序求它对每一个数字返回的值进行理解，树状数组的写法也相对固定，一般就是一个更行函数和一个求和函数。

下面来看看树状数组的另一种操作，插点问线问题，就是数组中的某个元素增加多少或者减少多少，然后求某个区间的和，其实也就是插线问点的相反操作。我们如果考虑用普通数组的话，需要更新增加的或减少的，然后循环区间求和，其主要时间复杂度在求和部分，也是O(n)。用树状数组的话，由于其特殊的结构使得节点不仅是自身，而且可以是某些元素的和，我们在求和的时候就不用求每个元素的和，只要按照其节点向下求即可这样就大大的提高了效率。线面来看上面题目116的代码:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    int largest;
    int a[1000001];
    int lowbit(int num)
    {
      return num&(-num);
    }
    void plus(int pos, int value)
    {
      while(pos<=largest)
      {
          a[pos]+=value;
          pos+=lowbit(pos);
      }
    }
    int sum(int num)
    {
       int s=0;
       while(num>0)
       {
          s+=a[num];
          num-=lowbit(num);
       }
       return s;
    }
    int main()
    {
        int m,n,i,start,last,k;
        char str[7];
        scanf("%d%d",&n,&m);
        largest=n;
        for(i=1; i<=n; i++)
        {
           scanf("%d",&k);
           plus(i,k);
        }
       while(m--)
       {
         scanf("%s%d%d",str,&start,&last);
         if(str[0]=='Q')
         {
            printf("%d\n",sum(last)-sum(start-1));
         }
        else  plus(start,last);
       }
       return 0;
    }

还有一个用法就是用树状数组求逆序数，这是一个相对不好理解，需要首先对树状数组及其结构理解透彻，也就是说对前面两种用法理解了的基础之上，下面开始讲解这个用法。

首先，求一组数的逆序数，就是求前面的数比数x大的个数的和或者x后面的数比x小的个数的和，就比如4,3,2,1中4前面比4大的没有，即为0,3前面比3大的有1个是4，2前面比2大有2个，1前面比一大的有3个，这样把0，1,2,3加起来即6就是这一组数的逆序数，我们用程序实现的话因为每一次都要跟前面的进行比较，如果这一组数足够多的话是非常消耗时间的，因此我们就想到了用树状数组去实现。

求逆序数是对树状数组的很巧妙的运用，首先是离散化操作，就那40,40,40,1,13,25,19,29这一组数来说吧，我们把他向着6，6,6,1,2,4,3,5就是它离散化的结果，这样做的好处就是对很大的值可以转化为比较小的容易处理的值，下面分析离散化的过程，首先我们用一个结构体里面有x，y；我们用x存上面的那些数，y存序号，结构体pp\[i\]

pp\[ i \]. x 40 40 40 1 13 25 19 29

pp \[ i \]. y 1 2 3 4 5 6 7 8

首先对其按pp\[i\].x进行排序，得到

pp\[ i \]. x 1 13 19 25 29 40 40 40

pp\[ i \]. y 4 5 7 6 8 1 2 3

然后我们按pp\[i\].y如果前后不相等就自加的办法得到

pp\[ i \]. y 4 5 7 6 8 1 2 3

k\[ i \] 1 2 3 4 5 6 6 6

然后pp\[ i \]. y递增的值就是我们所要的结果了

下面就是用树状数组求逆序数的过程，就比如说4,3,12，2,1这四个数，我们对其离散化操作后变为4,3,5,2,1，首先对树状数组tree全部初始化为0，我们首先对4进行操作，对tree\[4\]++;运用lowbit函数对其后边的值都进行更新，然后用sum函数找向前找比4小的数的个数，用1-sum(4)就是4前面的比它大的个数，重复上述操作把他们所有的值加起来的和就是它的逆序数了。

下面就是上面求逆序数题的代码，是一个求逆序数的模板题，贴在这儿，欢迎讨论；

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    int n;
    struct Node
    {
        long x;
        int y;
    };
    Node pp[1000005];
    int k[1000005];
    int num[1000005];
    int cmp(Node a1,Node a2)
    {
        return a1.x<a2.x;
    }
    int lowbit(int x)
    {
        return x&-x;
    }
    void update(int x)
    {
      while(x<=n)
      {
          num[x]++;
          x+=lowbit(x);
      }
    }
    int sum1(int x)
    {
        int a=0;
        while(x>0)
        {
            a+=num[x];
            x-=lowbit(x);
        }
        return a;
    }
    int main()
    {
        int T;
        long long count;
        scanf("%d",&T);
        while(T--)
        {
            count=0;
            memset(num,0,sizeof(num));
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&pp[i].x);
                pp[i].y=i;
            }
            memset(k,0,sizeof(k));  //<cstring>
            std::stable_sort(pp+1,pp+n+1,cmp);
            for(int i=1;i<=n;i++)
            {
                k[pp[i].y]=i;
            }
            int i;
            for(i=1;i<=n;i++)
            {
                //printf("%d ",k[i]);
                update(k[i]);
                count+=(i-sum1(k[i]));
            }
            printf("%lld\n",count);
        }
        return 0;
    }
    /*
    5
    8
    9 9 9 1 2 4 3 5
    */

[http_acm.nyist.net_JudgeOnline_problem.php_pid_117]: http://acm.nyist.net/JudgeOnline/problem.php?pid=117
[Image 1]: 
[2010102420055023.png]: /images/20220320/f9565a96b25e42c3b33a6ca6c0fc52fc.png