树状数组：求有数多少在a前面的数比a小的思路
2021-05-05 04:28
标签：text 读者 code under 必须 并且 模拟 sans nbsp 在看之前，你必须了解树状数组的基本函数 首先，假如求有多少在a前面的数比a小； 举例： 1 4 2 3 5 然后有5个空位置, _ _ _ _ _ 为sum[5] 第一步 求出sum[1]前缀，答案是0； 插入1, 1 _ _ _ _ 第二步 求出sum[4]前缀，答案是1； 插入4, 1 _ _ 4 _ 第二步 求出sum[2]前缀，答案是1； 插入4, 1 2 _ 4 _ .......................... 这样不断进行下去sum[i]就是 有多少在i前面的数比a小； 所以就转化成了求前缀和的题目了，自然就想到树状数组了； 但是输入的几个数可能会非常大，那么sum数组的下标就会爆； 我们只需知道每个数的大小关系，并不需要知道具体值，所以在处理之前可以离散化； 具体怎么实现，读者自行手动模拟； 按上面查找的思路 则反之 这样就ok了 树状数组：求有数多少在a前面的数比a小的思路 标签：text 读者 code under 必须 并且 模拟 sans nbsp 原文地址：https://www.cnblogs.com/wzx-RS-STHN/p/13193271.html求比a小在a前面数数量和比a小在a后面数数量的思路：
inline ll lowbit(ll x)
{
return x&(-x);
}
inline void insert(ll x,ll y)//加入
{
while(xn)
{
sum[x]+=y;
x+=lowbit(x);
}
}
inline ll findout(ll x)//查找
{
ll ans=0;
while(x)
{
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
inline ll cmp(oh a,oh b)//排序
{
if(a.v==b.v)
return a.numb.num;
else
return a.vb.v;
}
求有多少在a前面的数比a小
//离散化
for(ll i=1;i)
{
a[i].v=read();
a[i].num=i;//将每一个数的位置记下
}
sort(a+1,a+n+1,cmp);//从小到大排序，
//这样每个数都有顺序了，并且每个数对应的位置没有改变
for(ll i=1;i)
b[a[i].num]=i;//把第i小的数位置上赋值为i
for(ll i=1;i)
{
ll x=findout(b[i]);
ans[i]=x;//先求值，再插入，不然会把自己也算进去的
insert(b[i],1);
}
那么求比a小在a后面数数量
for(ll i=n;i>=1;i--)
{
ll x=findout(b[i]);
ans[i]=x;//反之
insert(b[i],1);
}
上一篇：算法记录
文章标题：树状数组：求有数多少在a前面的数比a小的思路
文章链接：http://soscw.com/index.php/essay/82575.html