ak2k8's blog

By ak2k8, history, 5 weeks ago, In English

Recently, I've just encountered this problem:$$$\newline$$$ Given a tree with $$$n$$$ vertices and rooted at $$$1$$$. Each vertex has an initial value, and initially, all these values are $$$0$$$.$$$\newline$$$ There are $$$q$$$ queries of two types:$$$\newline$$$ - "1 u": Find the sum of values of vertices in the subtree rooted at u.$$$\newline$$$ - "2 u": Find the value at vertex u.$$$\newline$$$ - "3 u v x": Increase the values of vertices on the simple path from u to v by x.$$$\newline$$$ Answer the queries of type 1 and 2.$$$\newline$$$ Constraints:

$$$ 1 \leq n,q \leq 200000 $$$
$$$ 1 \leq u,v \leq n $$$
$$$ 0 \leq |x| \leq 1000000 $$$

Time Limit:

$$$ 0.5s $$$

Are there any tricks to handle these types of queries with Euler Tour? I've thought about this problem for several days and haven't come up with any idea how to do it yet because of the update path queries. And with this time limit, I think HLD can't pass :<

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I can get you to q*log(q)*log(n). Probably some optimizations such as Fractional Cascading will get you to qlog(n), but I don't know them offhand. IMO an additional log(n) factor shouldn't matter in most contests, but ¯_(ツ)_/¯.

Put the nodes into an array in DFS-order, so that you can build a segment tree on top of them.

At each node in the segment tree, store a balanced tree with entries marking "A path from depth A to depth B (in the original tree) have X added to them" in sorted order of A, with sums of X on the intermediate nodes. Also with a depth D from the minimum-depth node in this range, keep a sum of X*(B-max(A,D)) across the segment.

When you encounter a query of type three, you can add these entries using LCA to find the depths A and B of each endpoint, then do point updates at each endpoint. Including maintaining the segment tree, this is log(n)*log(q) time. (log(n) for the segment tree, then log(q) for the entries in the trees inside the segment tree nodes).

When you encounter a query of type two you need to check the value of the node itself, which is a range query inside the segment tree. In each relevant segment tree node you query the tree "what is the sum of X for nodes that include my depth?". Similarly log(n)*log(q) time.

When you encounter a query of type one you do a similar range query on the segment tree, but instead of subtree queries you just add the stored sum X*(B-max(A,D)) from each segment tree node. This bit is only log(n) time.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much for the explanation, I'll try it.