动态前缀总和 [英] Dynamic prefix sum
问题描述
是否有任何数据结构能够返回数组的前缀和[1],更新元素以及将元素插入/删除到数组中,而这些操作全部都在O(log n)中?
Is there any data structure which is able to return the prefix sum [1] of array, update an element, and insert/remove elements to the array, all in O(log n)?
[1]前缀总和是从第一个元素到给定索引的所有元素的总和。
[1] "prefix sum" is the sum of all elements from the first one up to given index
例如,给定数组非负整数 8 1 10 7
的前三个元素的前缀总和为 19
( 8
+ 1
+ 10
)。将第一个元素更新为 7
,插入 3
作为第二个元素并删除第三个元素将得到 7 3 10 7
。同样,前三个元素的前缀和为 20
。
For example, given the array of non-negative integers 8 1 10 7
the prefix sum for first three elements is 19
(8
+ 1
+ 10
). Updating the first element to 7
, inserting 3
as the second element and removing the third one gives 7 3 10 7
. Again, the prefix sum of first three elements would be 20
.
对于前缀和更新,存在< a href = http://en.wikipedia.org/wiki/Fenwick_tree rel = nofollow> Fenwick树。但是我不知道如何用它来处理O(log n)中的添加/删除。
For prefix sum and update, there is Fenwick tree. But I don't know how to handle the addition/removal in O(log n) with it.
另一方面,有一些二进制搜索树,例如红黑树,它们全部负责更新/插入/删除在对数时间。但是我不知道如何维护给定的顺序并在O(log n)中做前缀总和。
On the other hand, there are several binary search trees such as Red-black tree, all of which handle the update/insert/remove in logarithmic time. But I don't know how to maintain the given ordering and do the prefix sum in O(log n).
推荐答案
A带有隐式密钥的诱捕可以在 O(log n)中执行所有这些操作。
每个查询的时间。隐式键的概念非常简单:我们不在节点中存储任何键。相反,我们维护所有节点的子树大小,并在使用此信息添加或删除元素时找到合适的位置。
A treap with implicit keys can perform all this operations in O(log n)
time per query. The idea of implicit keys is pretty simple: we do not store any keys in nodes. Instead, we maintain subtrees' sizes for all nodes and find an appropriate position when we add or remove an element using this information.
这是我的实现:
#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;
}
这篇关于动态前缀总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!