平衡二分木について
- cppの
std::set,std::mapに含まれているキーを二分木探索できる構造のこと
cppでの使い方
int main() {
set<int> st;
// s に 3 を挿入
st.insert(3);
// s に 5 を挿入
st.insert(5);
// 4 以上の要素のうち最小の要素のイテレータを取得
auto it = st.lower_bound(4);
auto prev = it; prev--;
// it の示す要素を出力
cout << *it << endl; // 5 を出力
// it の1つ前のイテレータの示す要素を出力
cout << *prev(it) << endl; // 3 を出力
}
pythonで実装する際のhow to
pythonのsetはstd::setのように二分木探索はできない
segment-treeで再現できるが、コーディングコストが非常に高い
平衡二分探索木が必要ならばcppで実装し始めたほうが早い
例; 典型使用例
問題
解説
- 特定の区間に含まれる区間の大きさを求めたい場合
回答
ll L, Q;
vector<ll> C, X;
int main() {
cin >> L >> Q;
C = vector<ll>(Q, 0);
X = vector<ll>(Q, 0);
set<ll> s;
s.insert(0);
s.insert(L);
rep(q, Q) {
cin >> C[q] >> X[q];
if( C[q] == 1L ) {
s.insert(X[q]);
} else {
auto it = s.lower_bound(X[q]);
auto prev = it; prev--;
print(*it - *prev);
}
}
}