implicit_treap.hpp¶
Implicit randomized treap supporting insertion, erasure, reversal, point updates, and ordered monoid products in expected O(log n) time.
Verified by deque, deque_operate_all_composite, range_reverse_range_sum.
把序列下标隐式存进随机平衡树，支持按位置切分、合并、插入删除与区间聚合。
Implementation¶
#ifndef NOYA_IMPLICIT_TREAP_HPP
#define NOYA_IMPLICIT_TREAP_HPP 1
/// @complexity Time: Expected O(log n) per split/merge/update/query.
/// Space: O(n) nodes and O(log n) expected stack.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap supporting insertion, erasure, reversal,
/// point updates, and ordered monoid products in expected O(log n) time.
template <class S, auto op, auto e> struct implicit_treap {
struct node {
S value;
S forward;
S backward;
std::uint64_t priority = 0;
int left = -1;
int right = -1;
int size = 1;
bool reversed = false;
};
std::vector<node> nodes;
int root = -1;
implicit_treap() = default;
explicit implicit_treap(const std::vector<S> &values) {
nodes.reserve(values.size());
for (const S &value : values) {
root = merge(root, make_node(value));
}
}
int size() const { return node_size(root); }
bool empty() const { return root == -1; }
/// @brief Insert value immediately before position.
void insert(int position, const S &value) {
assert(0 <= position && position <= size());
auto [left, right] = split(root, position);
root = merge(merge(left, make_node(value)), right);
}
/// @brief Erase and return the value at position.
S erase(int position) {
assert(0 <= position && position < size());
auto [left, suffix] = split(root, position);
auto [middle, right] = split(suffix, 1);
assert(middle != -1);
S value = nodes[middle].value;
root = merge(left, right);
return value;
}
/// @brief Replace the value at position.
void set(int position, const S &value) {
assert(0 <= position && position < size());
auto [left, suffix] = split(root, position);
auto [middle, right] = split(suffix, 1);
nodes[middle].value = value;
pull(middle);
root = merge(left, merge(middle, right));
}
/// @brief Return the value at position.
S get(int position) {
assert(0 <= position && position < size());
int current = root;
while (current != -1) {
push(current);
int left_size = node_size(nodes[current].left);
if (position < left_size) {
current = nodes[current].left;
} else if (position == left_size) {
return nodes[current].value;
} else {
position -= left_size + 1;
current = nodes[current].right;
}
}
assert(false);
return e();
}
/// @brief Reverse the half-open range [left, right).
void reverse(int left, int right) {
check_range(left, right);
auto [prefix, suffix] = split(root, left);
auto [middle, tail] = split(suffix, right - left);
apply_reverse(middle);
root = merge(prefix, merge(middle, tail));
}
/// @brief Return the ordered monoid product over [left, right).
S prod(int left, int right) {
check_range(left, right);
auto [prefix, suffix] = split(root, left);
auto [middle, tail] = split(suffix, right - left);
S result = forward_product(middle);
root = merge(prefix, merge(middle, tail));
return result;
}
/// @brief Materialize the current sequence.
std::vector<S> to_vector() {
std::vector<S> result;
result.reserve(size());
auto visit = [&](auto &self, int current) -> void {
if (current == -1) {
return;
}
push(current);
self(self, nodes[current].left);
result.push_back(nodes[current].value);
self(self, nodes[current].right);
};
visit(visit, root);
return result;
}
private:
std::uint64_t priority_state = 0x243f6a8885a308d3ULL;
int node_size(int current) const {
return current == -1 ? 0 : nodes[current].size;
}
S forward_product(int current) const {
return current == -1 ? e() : nodes[current].forward;
}
S backward_product(int current) const {
return current == -1 ? e() : nodes[current].backward;
}
std::uint64_t next_priority() {
std::uint64_t value = (priority_state += 0x9e3779b97f4a7c15ULL);
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
return value ^ (value >> 31);
}
int make_node(const S &value) {
nodes.push_back({value, value, value, next_priority()});
return int(nodes.size()) - 1;
}
void apply_reverse(int current) {
if (current == -1) {
return;
}
std::swap(nodes[current].left, nodes[current].right);
std::swap(nodes[current].forward, nodes[current].backward);
nodes[current].reversed = !nodes[current].reversed;
}
void push(int current) {
if (current != -1 && nodes[current].reversed) {
apply_reverse(nodes[current].left);
apply_reverse(nodes[current].right);
nodes[current].reversed = false;
}
}
void pull(int current) {
nodes[current].size =
1 + node_size(nodes[current].left) + node_size(nodes[current].right);
nodes[current].forward =
op(op(forward_product(nodes[current].left), nodes[current].value),
forward_product(nodes[current].right));
nodes[current].backward =
op(op(backward_product(nodes[current].right), nodes[current].value),
backward_product(nodes[current].left));
}
std::pair<int, int> split(int current, int left_size) {
if (current == -1) {
return {-1, -1};
}
push(current);
if (node_size(nodes[current].left) >= left_size) {
auto [left, right] = split(nodes[current].left, left_size);
nodes[current].left = right;
pull(current);
return {left, current};
}
auto [left, right] = split(nodes[current].right,
left_size - node_size(nodes[current].left) - 1);
nodes[current].right = left;
pull(current);
return {current, right};
}
int merge(int left, int right) {
if (left == -1 || right == -1) {
return left == -1 ? right : left;
}
if (nodes[left].priority > nodes[right].priority) {
push(left);
nodes[left].right = merge(nodes[left].right, right);
pull(left);
return left;
}
push(right);
nodes[right].left = merge(left, nodes[right].left);
pull(right);
return right;
}
void check_range(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
}
};
} // namespace noya
#endif // NOYA_IMPLICIT_TREAP_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>
/// @complexity Time: Expected O(log n) per split/merge/update/query.
/// Space: O(n) nodes and O(log n) expected stack.
namespace noya {
/// @brief Implicit randomized treap supporting insertion, erasure, reversal,
/// point updates, and ordered monoid products in expected O(log n) time.
template <class S, auto op, auto e> struct implicit_treap {
struct node {
S value;
S forward;
S backward;
std::uint64_t priority = 0;
int left = -1;
int right = -1;
int size = 1;
bool reversed = false;
};
std::vector<node> nodes;
int root = -1;
implicit_treap() = default;
explicit implicit_treap(const std::vector<S> &values) {
nodes.reserve(values.size());
for (const S &value : values) {
root = merge(root, make_node(value));
}
}
int size() const { return node_size(root); }
bool empty() const { return root == -1; }
/// @brief Insert value immediately before position.
void insert(int position, const S &value) {
assert(0 <= position && position <= size());
auto [left, right] = split(root, position);
root = merge(merge(left, make_node(value)), right);
}
/// @brief Erase and return the value at position.
S erase(int position) {
assert(0 <= position && position < size());
auto [left, suffix] = split(root, position);
auto [middle, right] = split(suffix, 1);
assert(middle != -1);
S value = nodes[middle].value;
root = merge(left, right);
return value;
}
/// @brief Replace the value at position.
void set(int position, const S &value) {
assert(0 <= position && position < size());
auto [left, suffix] = split(root, position);
auto [middle, right] = split(suffix, 1);
nodes[middle].value = value;
pull(middle);
root = merge(left, merge(middle, right));
}
/// @brief Return the value at position.
S get(int position) {
assert(0 <= position && position < size());
int current = root;
while (current != -1) {
push(current);
int left_size = node_size(nodes[current].left);
if (position < left_size) {
current = nodes[current].left;
} else if (position == left_size) {
return nodes[current].value;
} else {
position -= left_size + 1;
current = nodes[current].right;
}
}
assert(false);
return e();
}
/// @brief Reverse the half-open range [left, right).
void reverse(int left, int right) {
check_range(left, right);
auto [prefix, suffix] = split(root, left);
auto [middle, tail] = split(suffix, right - left);
apply_reverse(middle);
root = merge(prefix, merge(middle, tail));
}
/// @brief Return the ordered monoid product over [left, right).
S prod(int left, int right) {
check_range(left, right);
auto [prefix, suffix] = split(root, left);
auto [middle, tail] = split(suffix, right - left);
S result = forward_product(middle);
root = merge(prefix, merge(middle, tail));
return result;
}
/// @brief Materialize the current sequence.
std::vector<S> to_vector() {
std::vector<S> result;
result.reserve(size());
auto visit = [&](auto &self, int current) -> void {
if (current == -1) {
return;
}
push(current);
self(self, nodes[current].left);
result.push_back(nodes[current].value);
self(self, nodes[current].right);
};
visit(visit, root);
return result;
}
private:
std::uint64_t priority_state = 0x243f6a8885a308d3ULL;
int node_size(int current) const {
return current == -1 ? 0 : nodes[current].size;
}
S forward_product(int current) const {
return current == -1 ? e() : nodes[current].forward;
}
S backward_product(int current) const {
return current == -1 ? e() : nodes[current].backward;
}
std::uint64_t next_priority() {
std::uint64_t value = (priority_state += 0x9e3779b97f4a7c15ULL);
value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
return value ^ (value >> 31);
}
int make_node(const S &value) {
nodes.push_back({value, value, value, next_priority()});
return int(nodes.size()) - 1;
}
void apply_reverse(int current) {
if (current == -1) {
return;
}
std::swap(nodes[current].left, nodes[current].right);
std::swap(nodes[current].forward, nodes[current].backward);
nodes[current].reversed = !nodes[current].reversed;
}
void push(int current) {
if (current != -1 && nodes[current].reversed) {
apply_reverse(nodes[current].left);
apply_reverse(nodes[current].right);
nodes[current].reversed = false;
}
}
void pull(int current) {
nodes[current].size =
1 + node_size(nodes[current].left) + node_size(nodes[current].right);
nodes[current].forward =
op(op(forward_product(nodes[current].left), nodes[current].value),
forward_product(nodes[current].right));
nodes[current].backward =
op(op(backward_product(nodes[current].right), nodes[current].value),
backward_product(nodes[current].left));
}
std::pair<int, int> split(int current, int left_size) {
if (current == -1) {
return {-1, -1};
}
push(current);
if (node_size(nodes[current].left) >= left_size) {
auto [left, right] = split(nodes[current].left, left_size);
nodes[current].left = right;
pull(current);
return {left, current};
}
auto [left, right] = split(nodes[current].right,
left_size - node_size(nodes[current].left) - 1);
nodes[current].right = left;
pull(current);
return {current, right};
}
int merge(int left, int right) {
if (left == -1 || right == -1) {
return left == -1 ? right : left;
}
if (nodes[left].priority > nodes[right].priority) {
push(left);
nodes[left].right = merge(nodes[left].right, right);
pull(left);
return left;
}
push(right);
nodes[right].left = merge(left, nodes[right].left);
pull(right);
return right;
}
void check_range(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
}
};
} // namespace noya