Created
October 23, 2019 11:45
-
-
Save buttercrab/37cc5a029822be780edcf740ab9d09c2 to your computer and use it in GitHub Desktop.
persistent segment tree implementation in c++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int func(int a, int b) { | |
// binary function | |
// ex) return gcd(a, b); | |
// ex) return a * b; | |
// ex) return a ^ b; | |
// BUT! associated law has to be held | |
return a + b; | |
} | |
int inv_func(int a, int b) { | |
// inverse function of binary function | |
// func(a, b) == c then inv_func(c, b) == a | |
// ex) return a / b; | |
// ex) return a ^ b; | |
return a - b; | |
} | |
vector<int> seg, root{0}, left, right; | |
int new_node(int v = 0, int l = 0, int r = 0) { | |
seg.emplace_back(v); | |
::left.emplace_back(l); | |
::right.emplace_back(r); | |
return seg.size() - 1; | |
} | |
int make_tree(int node, int l, int r, int index, int diff) { | |
if(index < l || r < index) return node; | |
if(l == r) return new_node(seg[node] + diff); | |
int left = make_tree(::left[node], l, (l + r) >> 1, index, diff); | |
int right = make_tree(::right[node], ((l + r) >> 1) + 1, r, index, diff); | |
return new_node(func(seg[left], seg[right]), left, right); | |
} | |
int query(int node1, int node2, int l, int r, int start, int end) { | |
if(start <= l && r <= end) return inv_func(seg[node2], seg[node1]); | |
int mid = (l + r) >> 1; | |
if(mid < start) return query(::right[node1], ::right[node2], mid + 1, r, start, end); | |
if(mid + 1 > end) return query(::left[node1], ::left[node2], l, mid, start, end); | |
return func(query(::left[node1], ::left[node2], l, mid, start, end), | |
query(::right[node1], ::right[node2], mid + 1, r, start, end)); | |
} | |
int main() { | |
new_node(); | |
vector<int> v{1, 2, 3, 4}; | |
for(int i: v) { | |
root.emplace_back(make_tree(root.back(), 0, INT_MAX, i, 1)); | |
} | |
cout << query(root[0], root[3], 0, INT_MAX, 2, 3); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment