CHEFTRE - Editorial

aug16
cheftre
decomposition
editorial
hard
heavy-light
segment-tree

#1

(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Xellos

DIFFICULTY:

HARD

PREREQUISITES:

heavy-light decomposition, hashing, segment trees

PROBLEM:

Just another problem with queries on a tree. The queries are: reverse values on a path, copy values from a path, check if two paths contain the same sequence of values.

QUICK EXPLANATION:

Comparing paths = comparing hashes. Reversal queries are irrelevant. Use HLD to reduce the problem to subarray copy / compute hash queries, which can be solved using persistent DS, e.g. persistent segment trees.

EXPLANATION:

Queries of type 1 are just copying a path u\rightarrow v to the path v\rightarrow u, so we can just deal with them the same way as with type 2 queries.

This problem combines many advanced concepts. The first and probably most basic one is using heavy-light decomposition of the tree (rooted at e.g. 0) to split any path to O(\log{N}) paths, where each path goes towards or away from the root. When we have two paths of equal lengths, we can put them side by side and split each of them also at the same positions where the other is split; that gives still O(\log{N}) pairs of paths p_{1i},p_{2i} of equal lengths such that we need to copy the values in p_{1i} to p_{2i} for each i or check if they’re equal for each i.

The benefit of this splitting is that each path in the HLD is a linear structure - the copy/check operations are now on subarrays/segments (of possibly different arrays or the same array) instead of arbitrary paths in a tree.

SEGMENT OPERATIONS

First of all, checking subarrays/segments for equality directly is slow. We need some way to compare two segments in constant time, and the common choice for this is hashing. Let’s use a polynomial hash H(s)=\sum s_i q^i \% p for p=10^9+7 and some number q. If two segments have equal hashes, then they’re equal and if we know the lengths and hashes of two segments, we can compute their hash in constant time using precomputed powers of q. Let’s also not forget that the paths in the tree and therefore also segments here can be directed, so we need to store both forward and reverse hashes.

Let’s now build the typical data structure for segment operations: a segment tree which supports copying a segment (possibly from a different segment tree) and computing a segment’s hash. Most of the implementation is the same as for any other segment tree: if the current vertex doesn’t correspond to the current segment, split into sons and merge their hashes into the current vertex’s hash, return the hash of the current vertex when asked for it. The problem is the copy operation: what to do when a segment corresponding to some vertex v_1 has to be copied to another segment corresponding to some vertex v_2?

This trick is what persistent structures are based on: we simply replace the edge to v_1 from its parent (the vertex we got into it from) by an edge from that parent to v_2. Of course, when copying something into the subtree of such a vertex, we have to be careful: that vertex is shared by multiple segment trees, but we’re only modifying it in one of them. The solution is to create a copy of it with the same sons and only one parent - the one from the currently modified subtree. (Note that a vertex can technically have multiple parents, but they belong to different trees; this procedure also ensures that only the currently processed vertex can have multiple parents and not any vertices above it, since they’re the copies created here. We don’t have to remember the parents; they’re given implicitly when we go down a tree.)

In order to avoid having to reverse whole subtrees, we can mark vertices as “reverse this when necessary”; when processing such a vertex (after the above mentioned copying), we just swap its sons, mark them the same way and swap the forward/reverse hash. Also, two reversals cancel out.

We have everything necessary now. The total time complexity of any operation on such a segment tree is still O(\log{N}), since we’re only doing O(1) operations per vertex; with O(\log{N}) operations per query, the total time complexity is O(N+Q\log^2{N}). However, we’re adding O(\log{N}) vertices in each operation, so the memory complexity is also O(N+Q\log^2{N}).

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.

RELATED PROBLEMS:


#2

Can this be solved by Treaps ? If yes , then how ?


#3

Sure, it’s just another type of tree. A bit less balanced.

The real power of treaps is the ability to support much uglier operations and many of them at once (e.g. insert/erase/range updates/queries). In this case, you can use a persistent treap in exactly the same way as a persistent segment tree, since you don’t have those ugly operations.