NeoYL's blog

question about tree [solved]
By NeoYL, history, 20 months ago, In English

classical problem: add delta to all nodes on the path to u->v, it is basically adding delta to u and v, then val[lca(u,v)]-=delta, then just use dfs to find answer.

My question is to ask: is there a way to answer online?

Like let us say we have q<=1e5 queries and n<=1e5: is there a way to find value of a node during queries? (just curious)

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

Comments Comments (8)
| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use HLD (Heavy Light Decomposition).

→ Reply
»
20 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Actually, you can use the similar approach to the one you have mentioned to get an online solution. When a query "add $$$d$$$ to all vertexes on path from $$$u$$$ to $$$v$$$" comes, increase values of $$$u$$$ and $$$v$$$ by $$$d$$$ and decrease values of $$$LCA(u, v)$$$ and $$$ancestor(LCA(u, v))$$$ by $$$d$$$. In order to answer a query "get value of vertex $$$u$$$" we need to take a sum over it's subtree.

To efficiently get sums over subtrees and modify values in particular vertexes we can use the following construction. Let's traverse our tree using DFS. Notice, that all vertexes from a subtree of any vertex $$$u$$$ form a segment in the traversing. So to get a sum over a subtree of vertex $$$u$$$, we can just get a sum over a segment of the traversing from $$$tin[u]$$$ to $$$tout[u]$$$. Finally, to get sums over segments and modify elements in $$$O(log(n))$$$ we can use segment tree.

This way the solution will work with $$$O(q \cdot log(n))$$$ time and $$$O(n)$$$ or $$$O(n \cdot log(n))$$$ memory depending on the LCA implementation.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Actually, I didn't know about this approach, thank you for sharing!

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh, so instead you do it like flattening then do segtree. thanks for the answer

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what's online and offline query

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    online query means reading query one by one and processing them individually. offline query means reading all the query and processing them may be in reverse order or sorted order or some others way

    → Reply
»
20 months ago, # |
  Vote: I like it -19 Vote: I do not like it

use link-cut-tree, it is $$$O((n+q)\log n)$$$

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

use heavy light decomposition O(q * log^2n) complexity

→ Reply