Блог пользователя NeoYL

Автор NeoYL, история, 22 месяца назад, По-английски

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)

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use HLD (Heavy Light Decomposition).

»
22 месяца назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what's online and offline query

  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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

»
22 месяца назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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