top_k_sum.hpp¶
动态维护最大的 min(\(k\),N) 个元素之和，以稳定句柄精确删除；插入删除 O(log N)，调整 \(k\) 为均摊 O(1+所选数量变化)，求和 \(O(1)\)。
Complexity: Time: \(O(\log (n + 1))\) insert/erase; \(O(1 + d)\) amortized set_k, where \(d = \lvert \min (\mathrm{new}_{k} , n) - \min (\mathrm{old}_{k} , n)\rvert\). \(O(1)\) sum query. Space: \(O(n)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log(n+1)) insert/erase; O(1+d) amortized set_k,
/// where d = abs(min(new_k,n)-min(old_k,n)). O(1) sum query.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <iterator>
#include <set>
#include <utility>
namespace noya {
/// @brief Dynamic multiset maintaining the sum of the k largest values.
/// T arithmetic, including differences and intermediate sums, must fit.
/// At most INT_MAX insertions per object's lifetime; erase needs a live handle.
template <class T> struct top_k_sum {
using entry = std::pair<T, int>;
int k = 0;
int tot = 0;
T sum{};
std::set<entry> hi;
std::set<entry> lo;
top_k_sum() = default;
explicit top_k_sum(int k_) : k(k_) { assert(k >= 0); }
/// @brief Insert value and return a stable handle for exact erasure.
int insert(const T &val) {
int id = tot++;
entry item{val, id};
if (int(hi.size()) < k) {
sum += item.first;
hi.insert(std::move(item));
} else if (!hi.empty() && *hi.begin() < item) {
auto it = hi.begin();
sum += item.first - it->first;
lo.insert(lo.end(), hi.extract(it));
hi.insert(std::move(item));
} else {
lo.insert(std::move(item));
}
return id;
}
/// @brief Erase the entry identified by (value, handle).
void erase(const T &val, int id) {
entry tar{val, id};
if (auto it = hi.find(tar); it != hi.end()) {
sum -= it->first;
hi.erase(it);
} else {
auto ri = lo.find(tar);
assert(ri != lo.end());
lo.erase(ri);
}
rebalance();
}
void set_k(int k_) {
assert(k_ >= 0);
k = k_;
rebalance();
}
const T &query() const { return sum; }
int size() const { return int(hi.size() + lo.size()); }
private:
void rebalance() {
int tar = std::min(k, size());
while (int(hi.size()) < tar) {
auto it = std::prev(lo.end());
sum += it->first;
// This value precedes every selected entry, so begin() is exact.
hi.insert(hi.begin(), lo.extract(it));
}
while (int(hi.size()) > tar) {
auto it = hi.begin();
sum -= it->first;
lo.insert(lo.end(), hi.extract(it));
}
}
};
} // namespace noya
// NOYA_TOP_K_SUM_HPP
#ifndef NOYA_TOP_K_SUM_HPP
#define NOYA_TOP_K_SUM_HPP 1
/// @complexity Time: O(log(n+1)) insert/erase; O(1+d) amortized set_k,
/// where d = abs(min(new_k,n)-min(old_k,n)). O(1) sum query.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <iterator>
#include <set>
#include <utility>
namespace noya {
/// @brief Dynamic multiset maintaining the sum of the k largest values.
/// T arithmetic, including differences and intermediate sums, must fit.
/// At most INT_MAX insertions per object's lifetime; erase needs a live handle.
template <class T> struct top_k_sum {
using entry = std::pair<T, int>;
int k = 0;
int tot = 0;
T sum{};
std::set<entry> hi;
std::set<entry> lo;
top_k_sum() = default;
explicit top_k_sum(int k_) : k(k_) { assert(k >= 0); }
/// @brief Insert value and return a stable handle for exact erasure.
int insert(const T &val) {
int id = tot++;
entry item{val, id};
if (int(hi.size()) < k) {
sum += item.first;
hi.insert(std::move(item));
} else if (!hi.empty() && *hi.begin() < item) {
auto it = hi.begin();
sum += item.first - it->first;
lo.insert(lo.end(), hi.extract(it));
hi.insert(std::move(item));
} else {
lo.insert(std::move(item));
}
return id;
}
/// @brief Erase the entry identified by (value, handle).
void erase(const T &val, int id) {
entry tar{val, id};
if (auto it = hi.find(tar); it != hi.end()) {
sum -= it->first;
hi.erase(it);
} else {
auto ri = lo.find(tar);
assert(ri != lo.end());
lo.erase(ri);
}
rebalance();
}
void set_k(int k_) {
assert(k_ >= 0);
k = k_;
rebalance();
}
const T &query() const { return sum; }
int size() const { return int(hi.size() + lo.size()); }
private:
void rebalance() {
int tar = std::min(k, size());
while (int(hi.size()) < tar) {
auto it = std::prev(lo.end());
sum += it->first;
// This value precedes every selected entry, so begin() is exact.
hi.insert(hi.begin(), lo.extract(it));
}
while (int(hi.size()) > tar) {
auto it = hi.begin();
sum -= it->first;
lo.insert(lo.end(), hi.extract(it));
}
}
};
} // namespace noya
#endif // NOYA_TOP_K_SUM_HPP
/// @complexity Time: O(log(n+1)) insert/erase; O(1+d) amortized set_k,
/// where d = abs(min(new_k,n)-min(old_k,n)). O(1) sum query.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <iterator>
#include <set>
#include <utility>
namespace noya {
/// @brief Dynamic multiset maintaining the sum of the k largest values.
/// T arithmetic, including differences and intermediate sums, must fit.
/// At most INT_MAX insertions per object's lifetime; erase needs a live handle.
template <class T> struct top_k_sum {
using entry = std::pair<T, int>;
int k = 0;
int tot = 0;
T sum{};
std::set<entry> hi;
std::set<entry> lo;
top_k_sum() = default;
explicit top_k_sum(int k_) : k(k_) { assert(k >= 0); }
/// @brief Insert value and return a stable handle for exact erasure.
int insert(const T &val) {
int id = tot++;
entry item{val, id};
if (int(hi.size()) < k) {
sum += item.first;
hi.insert(std::move(item));
} else if (!hi.empty() && *hi.begin() < item) {
auto it = hi.begin();
sum += item.first - it->first;
lo.insert(lo.end(), hi.extract(it));
hi.insert(std::move(item));
} else {
lo.insert(std::move(item));
}
return id;
}
/// @brief Erase the entry identified by (value, handle).
void erase(const T &val, int id) {
entry tar{val, id};
if (auto it = hi.find(tar); it != hi.end()) {
sum -= it->first;
hi.erase(it);
} else {
auto ri = lo.find(tar);
assert(ri != lo.end());
lo.erase(ri);
}
rebalance();
}
void set_k(int k_) {
assert(k_ >= 0);
k = k_;
rebalance();
}
const T &query() const { return sum; }
int size() const { return int(hi.size() + lo.size()); }
private:
void rebalance() {
int tar = std::min(k, size());
while (int(hi.size()) < tar) {
auto it = std::prev(lo.end());
sum += it->first;
// This value precedes every selected entry, so begin() is exact.
hi.insert(hi.begin(), lo.extract(it));
}
while (int(hi.size()) > tar) {
auto it = hi.begin();
sum -= it->first;
lo.insert(lo.end(), hi.extract(it));
}
}
};
} // namespace noya
// NOYA_TOP_K_SUM_HPP