# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-08-12 03:50
|
And implementation of the range sum Persistent Segment Tree. Provides \(O(\log n)\) assignment and historic range query operations.
#include<deque>
struct PersistentSegmentTree {
struct Node {
long long value = 0;
Node* lch = 0;
Node* rch = 0;
};
int n;
std::deque<Node> nodes;
PersistentSegmentTree(int nsize) {
n = 1;
while(n < nsize) {
n *= 2;
}
nodes.resize(2*n);
for(int i=n-1; i>0; i--) {
nodes[i].lch = &nodes[2*i];
nodes[i].rch = &nodes[2*i+1];
}
}
Node* set(int pos, int to_set, Node* node, int lb = 0, int rb = -1) {
// [lb, rb) represents the range of the current node
if(rb == -1) rb = n;
nodes.push_back(*node); // Create a new version of the node
Node* cur = &nodes.back();
if(rb - lb == 1) { // We are at leaf, so perform the set
cur->value = to_set;
return cur;
}
int mid = (lb + rb) / 2;
if(pos < mid) {
cur->lch = set(pos, to_set, cur->lch, lb, mid); // Recursive call on left subtree
} else {
cur->rch = set(pos, to_set, cur->rch, mid, rb); // Recursive call on right subtree
}
cur->value = cur->lch->value + cur->rch->value;
return cur; // Return the new version of the node.
}
long long get(int l, int r, Node* cur, int lb = 0, int rb = -1) {
// [lb, rb) represents the range of the current node
if(rb == -1) rb = n;
if(l <= lb && rb <= r) { // Segment of the node is fully within the queried range
return cur->value;
}
int mid = (lb + rb) / 2;
long long result = 0;
if(l < mid) {
result += get(l, r, cur->lch, lb, mid); // Recursive call on left subtree
}
if(mid < r) {
result += get(l, r, cur->rch, mid, rb); // Recursive call on right subtree
}
return result;
}
};
int main() {
PersistentSegmentTree stree(10);
std::deque<PersistentSegmentTree::Node*> root_versions = {&stree.nodes[1]}; // Track tree root versions
root_versions.push_back(stree.set(3, 5, root_versions.back())); // Set a value
root_versions.push_back(stree.set(4, 6, root_versions.back())); // Set a value
root_versions.push_back(stree.set(5, 7, root_versions.back())); // Set a value
int range_sum = stree.get(2, 7, root_versions[root_versions.size()-2]); // Query range before the last operation
}
Data Structures, Advanced Concepts: Persistent Segment Tree - courses.cs.ut.ee
Segment Tree: Preserving the history of its values (Persistent Segment Tree) - cp-algorithms.com
classes | ||
std::deque |
en.cppreference.com | cplusplus.com |
functions | ||
std::deque::push_back |
en.cppreference.com | cplusplus.com |
Implement a Persistent Segment Tree for tracking range sums. Perform an assignment operation 3 times, and then output the sum of some range before the last assignment operation (after it has been performed).