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

本文主要是介绍算法提高之楼兰图腾(树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

楼兰图腾(树状数组)

• 核心算法：树状数组

  • 将下标转化为二进制 例如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/

这篇关于算法提高之楼兰图腾(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---