Yes, basic knowledge is enough. If you have done RSQ or RMQ, even without lazy propagation, I believe you can understand how persistence works
Amazing article!
Good question. To revert, you pass the root of an old version. Let’s say range set update, sample usage below:
int arr[] = {7, 1, 5, 2, 3}; n=5;
int tree0 = build(arr);
int tree1 = update(1, -4, tree0); // {7, -4, 5, 2, 3}
int tree2 = update(2, -10, tree1); // {7, -4, -10, 2, 3};
int tree3 = update(4, -25, tree2); // {7, -4, -10, 2, -25};
// revert range [0..2] back to initial [tree0]
int tree4 = rangecopy(0, 2, tree3, tree0); // {7, 1, 5, 2, -25}
During recursion, the nodes of tree4 inside the range [0:2] will be the nodes from tree0. Hope that answers it ^
Linking some starting problems will make the amazing tutorial more complete, i guess. examples : MKTHNUM, SORTING etc.
Yes, that answers my question. Thanks a lot.
This is great! Will add these problems to the list
It’s the same as segment tree. We’re not really creating new nodes during query (except when lazy), so it’s the same code. Except that instead of passing 2p and 2p + 1, we pass l[p] and r[p] during recursion:
// Example RSQ, call sum_query(a, b, root)
int sum_query(int a, int b, int p, int L=0, int R=n-1) {
if (b < L || R < a) return 0; // outside range
if (a <= L && R <= b) return st[p]; // inside range
return sum_query(a, b, l[p], L, M)
+ sum_query(a, b, r[p], M + 1, R);
}
Thanks!! I will re-attempt the questions with this in mind (got stuck at thinking part) ^^
Very nice ^^
Let’s say I want to compare if array [1, 2, 2, 3, 4]
is similar to [1, 2, 3, 3, 4]
. My trees represent hashing of frequency tables {1:1, 2:2, 3:1, 4:1}
and {1:1, 2:1, 3:2, 4:1}
Tree 1 Tree 2
[1, 2, 1, 1] [1, 1, 2, 1]
/ \ / \
[1, 2] [1, 1] [1, 1] [2, 1]
/ \ / \ / \ / \
... ...
Look at second layer, there’s a special case where both left and right have mismatch, but the result is still “similar”. This can be solved by comparing rightmost and leftmost in both trees.
You’ll need to do LCA with jumping pointers. You have tree[a]
contain all nodes from root to a
(you can use range sum). Then to find out if c
is in the path from a
to b
, you check if query(c, tree[a]) + query(c, tree[b]) - query(c, tree[parent(LCA(a, b))]) == 1
with principle of inclusion-exclusion
Thanks mate, It is clear now. I’m gonna write a small post on persistent hash tree.
Great ! thanks
So when we are building PST(initially) we always build a copy of original SegT ? (As we are doing in build()
function by calling newleaf()
and newparent()
)
By convention yes, if you have an initial array. But if tree is empty at the start, you can make also do without build by assigning tree as null (0
) at the start, and do point updates one by one (e.g. path-to-root problems)
and st[]
here stores the sum of elements in pre-order fashion, not conventional parent to child [2*i,2*i+1]
way, does it make things easy ?
KQUERY can’t be solved using persistent segment tree? I am getting TLE.
hey i have done DQUERY using MO’s algorithm,but i am unable to solve that using persistent segment tree.can you please share your code?