treap 암시 적 키를 사용하면이 작업을 모두 쿼리 당 O(log n) 시간으로 수행 할 수 있습니다. 암시 적 키의 개념은 매우 간단합니다. 노드에 키를 저장하지 않습니다. 대신 모든 노드에 대해 하위 트리의 크기를 유지하고이 정보를 사용하여 요소를 추가하거나 제거 할 때 적절한 위치를 찾습니다.
#include <iostream>
#include <memory>
struct Node {
int priority;
int val;
long long sum;
int size;
std::shared_ptr<Node> left;
std::shared_ptr<Node> right;
Node(long val):
priority(rand()), val(val), sum(val), size(1), left(), right() {}
};
// Returns the size of a node owned by t if it is not empty and 0 otherwise.
int getSize(std::shared_ptr<Node> t) {
if (!t)
return 0;
return t->size;
}
// Returns the sum of a node owned by t if it is not empty and 0 otherwise.
long long getSum(std::shared_ptr<Node> t) {
if (!t)
return 0;
return t->sum;
}
// Updates a node owned by t if it is not empty.
void update(std::shared_ptr<Node> t) {
if (t) {
t->size = 1 + getSize(t->left) + getSize(t->right);
t->sum = t->val + getSum(t->left) + getSum(t->right);
}
}
// Merges the nodes owned by L and R and returns the result.
std::shared_ptr<Node> merge(std::shared_ptr<Node> L,
std::shared_ptr<Node> R) {
if (!L || !R)
return L ? L : R;
if (L->priority > R->priority) {
L->right = merge(L->right, R);
update(L);
return L;
} else {
R->left = merge(L, R->left);
update(R);
return R;
}
}
// Splits a subtree rooted in t by pos.
std::pair<std::shared_ptr<Node>, std::shared_ptr<Node>> split(
std::shared_ptr<Node> t,
int pos, int add) {
if (!t)
return make_pair(std::shared_ptr<Node>(), std::shared_ptr<Node>());
int cur = getSize(t->left) + add;
std::pair<std::shared_ptr<Node>, std::shared_ptr<Node>> res;
if (pos <= cur) {
auto ret = split(t->left, pos, add);
t->left = ret.second;
res = make_pair(ret.first, t);
} else {
auto ret = split(t->right, pos, cur + 1);
t->right = ret.first;
res = make_pair(t, ret.second);
}
update(t);
return res;
}
// Returns a prefix sum of [0 ... pos]
long long getPrefixSum(std::shared_ptr<Node>& root, int pos) {
auto parts = split(root, pos + 1, 0);
long long res = getSum(parts.first);
root = merge(parts.first, parts.second);
return res;
}
// Adds a new element at a position pos with a value newValue.
// Indices are zero-based.
void addElement(std::shared_ptr<Node>& root, int pos, int newValue) {
auto parts = split(root, pos, 0);
std::shared_ptr<Node> newNode = std::make_shared<Node>(newValue);
auto temp = merge(parts.first, newNode);
root = merge(temp, parts.second);
}
// Removes an element at the given position pos.
// Indices are zero-based.
void removeElement(std::shared_ptr<Node>& root, int pos) {
auto parts1 = split(root, pos, 0);
auto parts2 = split(parts1.second, 1, 0);
root = merge(parts1.first, parts2.second);
}
int main() {
std::shared_ptr<Node> root;
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::string s;
std::cin >> s;
if (s == "add") {
int pos, val;
std::cin >> pos >> val;
addElement(root, pos, val);
} else if (s == "remove") {
int pos;
std::cin >> pos;
removeElement(root, pos);
} else {
int pos;
std::cin >> pos;
std::cout << getPrefixSum(root, pos) << std::endl;
}
}
return 0;
}
미안하지만 난 완전히 따르지 않는하십시오 treap 내가 "첫 번째 요소를 업데이트 할 방법 즉 무작위로 순서를 가지고 "? "적절한 위치를 찾아라"- 어떻게? –
@EcirHana 트랩에 임의의 순서가 없습니다. – kraskevich
"각 키에 (임의로 선택한) 숫자 우선 순위가 부여 된 데카르트 트리입니다." –