2 月 7 日算法练习- 数据结构-树状数组上二分
问题引入
给出三种操作，
0在容器中插入一个数。
1在容器中删除一个数。
2求出容器中大于a的第k大元素。
树状数组的特点就是对点更新，成段求和，而且常数非常小。原始的树状数组只有两种操作，在某点插入一个数和求1到i的所有数的和。
这道题目一共有三种操作，但是实质上其实只有两种：插入和询问。插入操作和删除操作可以视为一种，只不过一个是将标记+1，另一个是－1，而插入的数对应于树状数组的下标，这样就可以在log（n）的时间内完成插入和删除。
求大于a的k大元素，可以通过二分枚举答案来完成，枚举的是当前答案在树状数组中的位置，设为m，然后对v［a+1］- v［m］求和就是小
于等于m的数的个数，这一步可以用树状数组的求和操作来完成，然后根据和k的比较来调整m的位置。询问的复杂度也是log（n）的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110000;
int tree[maxn];
int q;int lowbit(int x){return x&-x;
}void add(int pos,int x){while(pos<maxn){tree[pos] += x;pos += lowbit(pos);}return;
}
int query(int pos){int res = 0;while(pos){res+=tree[pos];pos -= lowbit(pos);}return res;
}int find(int a,int k){int l = a+1,r = maxn-1;int ans = -1;while(l<=r){int mid = (l+r)>>1;if(query(mid)-query(a)==k)ans = mid;if(query(mid)-query(a)>=k)r = mid-1;else l = mid +1;}return ans;
}int main( ){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>q;while(q--){int x,y,z;cin>>x;if(x==0){cin>>y;add(y,1);}else if(x==1){cin>>y;if((query(y)-query(y-1))==0)continue;add(y,-1);}else{cin>>y>>z;cout<<find(y,z)<<'\n';}}return 0;
}算法分析
树状数组+二分复杂度可以比较直接的得到为 nlog2n
修改数组
思路：利用树状数组+二分。利用树状数组来快速求得区间和从而利用二分来找到第一个大于 i 的数的位置。
#include<iostream>
using namespace std;
const int maxn = 1e5+9;
int a[maxn],vis[maxn],tree[maxn];
int n;int lowbit(int x){return x&-x;
}void add(int k,int x){while(k<maxn){tree[k]+=x;k += lowbit(k);}
}int query(int k){int ans = 0;while(k){ans+=tree[k];k-=lowbit(k);}return ans;
}int main( ){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(!vis[a[i]])vis[a[i]]=1,add(a[i],1);else{int l=a[i],r =maxn,ans = -1;while(l<=r){int mid = (l+r)>>1;if(query(mid)-query(a[i]-1)<mid-a[i]+1)r = mid-1,ans = mid;else l = mid+1;}a[i] = ans;vis[ans]=1;add(ans,1);}}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];return 1;
}