算法提高之楼兰图腾(树状数组)

楼兰图腾(树状数组)

• 核心算法：树状数组

  • 将下标转化为二进制 例如11100100 父节点下标x 子节点下标i
    • 由下图可知 每一个数都可以由其子节点**(如果有)**求和得到
    • **由父节点找子节点：**每个子节点下标 –> x – 1 – lowbit(x – 1)
    • 由子节点找父节点： i + lowbit(i)
  • 

•   #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    typedef long long LL;
    const int N = 200010;
    
    int Greater[N],lower[N];
    int a[N];
    int tr[N];
    int n;
    
    int lowbit(int x)
    {
        return x&-x;  //取最后一位1
    }
    
    void add(int x,int c)
    {
        for(int i=x;i<=n;i += lowbit(i)) tr[i] += c;  //在每一个父节点上都加上c
    } 
    
    int sum(int x)
    {
        int res=0;
        for(int i=x;i;i -= lowbit(i)) res+=tr[i];  //所有子节点求和
        return res;
    }
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        
        for(int i=1;i<=n;i++)
        {
            int y = a[i];
            Greater[i] = sum(n) - sum(y);  //前缀和 求值为y-n的个数
            lower[i] = sum(y-1);  //0-(y-1)的个数
            //解释:大小为y的有1个
            add(y,1);  //值作为下标 个数作为值 存入树状数组
        }
        //清空之前的树
        memset(tr,0,sizeof tr);
        LL res1=0,res2=0;
        for(int i=n;i;i--)
        {
            int y = a[i];
            //Greater里面存的是左边大的 再求一个右边大的
            res1 += Greater[i] * (LL)(sum(n) - sum(y));  
            res2 += lower[i] * (LL)(sum(y-1));
            //一样的操作建树
            add(y,1);
        }
        cout<<res1<<" "<<res2;
    }
  

参考题解:https://www.acwing.com/solution/content/110791/