point_set_range_freq.hpp¶
Point assignment and exact-value frequency queries on half-open ranges, both in expected O(log n) time.
Verified by point_set_range_frequency.
维护数组的单点赋值，并统计区间内某个值的出现次数；适合动态序列上的区间频率查询。
Implementation¶
#ifndef NOYA_POINT_SET_RANGE_FREQUENCY_HPP
#define NOYA_POINT_SET_RANGE_FREQUENCY_HPP 1
/// @complexity Time: Expected O(n log n) build and O(log n) assignment/frequency query.
/// Space: O(n).
#include <cassert>
#include <cstdint>
#include <map>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Point assignment and exact-value frequency queries on half-open
/// ranges, both in expected O(log n) time.
template <class T> struct point_set_range_frequency {
struct node {
int left = -1;
int right = -1;
int size = 1;
std::uint64_t priority = 0;
};
int n = 0;
std::vector<T> values;
std::vector<node> nodes;
std::map<T, int> roots;
point_set_range_frequency() = default;
explicit point_set_range_frequency(
const std::vector<T> &input,
std::uint64_t seed = 0x243f6a8885a308d3ULL) {
build(input, seed);
}
/// @brief Rebuild the index from input in expected O(n log n) time.
void build(const std::vector<T> &input,
std::uint64_t seed = 0x243f6a8885a308d3ULL) {
n = int(input.size());
values = input;
nodes.assign(n, {});
roots.clear();
std::mt19937_64 random(seed);
for (int index = 0; index < n; index++) {
nodes[index].priority = random();
auto [iterator, inserted] = roots.try_emplace(values[index], -1);
iterator->second = insert(iterator->second, index);
}
}
/// @brief Assign value to position index in expected O(log n) time.
void set(int index, const T &value) {
assert(0 <= index && index < n);
if (values[index] == value) {
return;
}
auto old_iterator = roots.find(values[index]);
assert(old_iterator != roots.end());
old_iterator->second = erase(old_iterator->second, index);
if (old_iterator->second == -1) {
roots.erase(old_iterator);
}
nodes[index].left = nodes[index].right = -1;
nodes[index].size = 1;
auto [new_iterator, inserted] = roots.try_emplace(value, -1);
new_iterator->second = insert(new_iterator->second, index);
values[index] = value;
}
/// @brief Count occurrences of value in [left, right) in expected O(log n)
/// time.
int query(int left, int right, const T &value) const {
assert(0 <= left && left <= right && right <= n);
auto iterator = roots.find(value);
if (iterator == roots.end()) {
return 0;
}
return count_less(iterator->second, right) -
count_less(iterator->second, left);
}
/// @brief Return the current value at one position.
const T &get(int index) const {
assert(0 <= index && index < n);
return values[index];
}
private:
int subtree_size(int root) const {
return root == -1 ? 0 : nodes[root].size;
}
void pull(int root) {
nodes[root].size =
1 + subtree_size(nodes[root].left) + subtree_size(nodes[root].right);
}
bool higher_priority(int first, int second) const {
return nodes[first].priority != nodes[second].priority
? nodes[first].priority > nodes[second].priority
: first < second;
}
std::pair<int, int> split(int root, int key) {
if (root == -1) {
return {-1, -1};
}
if (root < key) {
auto [left, right] = split(nodes[root].right, key);
nodes[root].right = left;
pull(root);
return {root, right};
}
auto [left, right] = split(nodes[root].left, key);
nodes[root].left = right;
pull(root);
return {left, root};
}
int merge(int left, int right) {
if (left == -1) {
return right;
}
if (right == -1) {
return left;
}
if (higher_priority(left, right)) {
nodes[left].right = merge(nodes[left].right, right);
pull(left);
return left;
}
nodes[right].left = merge(left, nodes[right].left);
pull(right);
return right;
}
int insert(int root, int index) {
if (root == -1) {
return index;
}
if (higher_priority(index, root)) {
auto [left, right] = split(root, index);
nodes[index].left = left;
nodes[index].right = right;
pull(index);
return index;
}
if (index < root) {
nodes[root].left = insert(nodes[root].left, index);
} else {
nodes[root].right = insert(nodes[root].right, index);
}
pull(root);
return root;
}
int erase(int root, int index) {
assert(root != -1);
if (root == index) {
return merge(nodes[root].left, nodes[root].right);
}
if (index < root) {
nodes[root].left = erase(nodes[root].left, index);
} else {
nodes[root].right = erase(nodes[root].right, index);
}
pull(root);
return root;
}
int count_less(int root, int key) const {
int result = 0;
while (root != -1) {
if (root < key) {
result += 1 + subtree_size(nodes[root].left);
root = nodes[root].right;
} else {
root = nodes[root].left;
}
}
return result;
}
};
} // namespace noya
#endif // NOYA_POINT_SET_RANGE_FREQUENCY_HPP
#include <cassert>
#include <cstdint>
#include <map>
#include <random>
#include <utility>
#include <vector>
/// @complexity Time: Expected O(n log n) build and O(log n) assignment/frequency query.
/// Space: O(n).
namespace noya {
/// @brief Point assignment and exact-value frequency queries on half-open
/// ranges, both in expected O(log n) time.
template <class T> struct point_set_range_frequency {
struct node {
int left = -1;
int right = -1;
int size = 1;
std::uint64_t priority = 0;
};
int n = 0;
std::vector<T> values;
std::vector<node> nodes;
std::map<T, int> roots;
point_set_range_frequency() = default;
explicit point_set_range_frequency(
const std::vector<T> &input,
std::uint64_t seed = 0x243f6a8885a308d3ULL) {
build(input, seed);
}
/// @brief Rebuild the index from input in expected O(n log n) time.
void build(const std::vector<T> &input,
std::uint64_t seed = 0x243f6a8885a308d3ULL) {
n = int(input.size());
values = input;
nodes.assign(n, {});
roots.clear();
std::mt19937_64 random(seed);
for (int index = 0; index < n; index++) {
nodes[index].priority = random();
auto [iterator, inserted] = roots.try_emplace(values[index], -1);
iterator->second = insert(iterator->second, index);
}
}
/// @brief Assign value to position index in expected O(log n) time.
void set(int index, const T &value) {
assert(0 <= index && index < n);
if (values[index] == value) {
return;
}
auto old_iterator = roots.find(values[index]);
assert(old_iterator != roots.end());
old_iterator->second = erase(old_iterator->second, index);
if (old_iterator->second == -1) {
roots.erase(old_iterator);
}
nodes[index].left = nodes[index].right = -1;
nodes[index].size = 1;
auto [new_iterator, inserted] = roots.try_emplace(value, -1);
new_iterator->second = insert(new_iterator->second, index);
values[index] = value;
}
/// @brief Count occurrences of value in [left, right) in expected O(log n)
/// time.
int query(int left, int right, const T &value) const {
assert(0 <= left && left <= right && right <= n);
auto iterator = roots.find(value);
if (iterator == roots.end()) {
return 0;
}
return count_less(iterator->second, right) -
count_less(iterator->second, left);
}
/// @brief Return the current value at one position.
const T &get(int index) const {
assert(0 <= index && index < n);
return values[index];
}
private:
int subtree_size(int root) const {
return root == -1 ? 0 : nodes[root].size;
}
void pull(int root) {
nodes[root].size =
1 + subtree_size(nodes[root].left) + subtree_size(nodes[root].right);
}
bool higher_priority(int first, int second) const {
return nodes[first].priority != nodes[second].priority
? nodes[first].priority > nodes[second].priority
: first < second;
}
std::pair<int, int> split(int root, int key) {
if (root == -1) {
return {-1, -1};
}
if (root < key) {
auto [left, right] = split(nodes[root].right, key);
nodes[root].right = left;
pull(root);
return {root, right};
}
auto [left, right] = split(nodes[root].left, key);
nodes[root].left = right;
pull(root);
return {left, root};
}
int merge(int left, int right) {
if (left == -1) {
return right;
}
if (right == -1) {
return left;
}
if (higher_priority(left, right)) {
nodes[left].right = merge(nodes[left].right, right);
pull(left);
return left;
}
nodes[right].left = merge(left, nodes[right].left);
pull(right);
return right;
}
int insert(int root, int index) {
if (root == -1) {
return index;
}
if (higher_priority(index, root)) {
auto [left, right] = split(root, index);
nodes[index].left = left;
nodes[index].right = right;
pull(index);
return index;
}
if (index < root) {
nodes[root].left = insert(nodes[root].left, index);
} else {
nodes[root].right = insert(nodes[root].right, index);
}
pull(root);
return root;
}
int erase(int root, int index) {
assert(root != -1);
if (root == index) {
return merge(nodes[root].left, nodes[root].right);
}
if (index < root) {
nodes[root].left = erase(nodes[root].left, index);
} else {
nodes[root].right = erase(nodes[root].right, index);
}
pull(root);
return root;
}
int count_less(int root, int key) const {
int result = 0;
while (root != -1) {
if (root < key) {
result += 1 + subtree_size(nodes[root].left);
root = nodes[root].right;
} else {
root = nodes[root].left;
}
}
return result;
}
};
} // namespace noya