Solving tasks with trees without HLD

Revision en1, by AndreyPavlov, 2022-08-01 13:27:42

Problem

When you learn about Heavy Light Decomposition tree problems take on new meaning. But writing HLD every tree problem with queries so boring. In this post, I will show some problems (as well as ideas for solving them) in which you can write HLD, but with a little thought, the solution becomes easier.

Modifications and receiving at the point

Task: A tree is given, as well as requests to add in a subtree and on the path to the root, as well as to find out the value at the top.

First idea — HLD! But stop, we only need the value at the point, maybe can easier? Yes, we will solve task in offline mode.

Idea: How to find out what changes occurred at the top at time t? Need to store some structure, for example, segment tree and answer for query in time t is sum on prefix t. Now we have add in subtree and on the path to the root. For subtere adding we will remember for each vertex that in its subtree we need to add the number x and the query time.

Tags segment tree, fenwick tree, heavy-light, hld, tree, query, add, offline

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English AndreyPavlov 2022-08-03 17:48:41 4
en17 English AndreyPavlov 2022-08-03 16:37:48 2 Tiny change: 'fter.\n\n[1. Max Flow' -> 'fter.\n\n[A. Max Flow'
en16 English AndreyPavlov 2022-08-02 16:31:31 128
en15 English AndreyPavlov 2022-08-02 14:13:42 3 Tiny change: ' \cdot log n)$\n\n### ' -> ' \cdot log{n})$\n\n### '
en14 English AndreyPavlov 2022-08-01 21:19:04 12
en13 English AndreyPavlov 2022-08-01 19:59:46 149
en12 English AndreyPavlov 2022-08-01 19:53:42 2 Tiny change: 'n point.\n[C. Prop' -> 'n point.\n\n[C. Prop'
en11 English AndreyPavlov 2022-08-01 19:53:01 139
en10 English AndreyPavlov 2022-08-01 19:48:40 3 Tiny change: ' dfs(child, u);\n ' -> ' dfs(child);\n '
en9 English AndreyPavlov 2022-08-01 19:46:20 156
en8 English AndreyPavlov 2022-08-01 19:44:20 4 Tiny change: 'o without lca.\n\n**Ide' -> 'o without hld.\n\n**Ide'
en7 English AndreyPavlov 2022-08-01 19:42:46 0 (published)
en6 English AndreyPavlov 2022-08-01 19:41:14 3 (saved to drafts)
en5 English AndreyPavlov 2022-08-01 19:29:07 0 (published)
en4 English AndreyPavlov 2022-08-01 19:28:38 80 Tiny change: 'ick tree\n\n### **' -> 'ick tree\nAsymptotics is $O(n + q log n)$\n\n### **'
en3 English AndreyPavlov 2022-08-01 18:31:58 1641 Tiny change: 'roblem**\n\nWhen y' -> 'roblem**\n===========\n\nWhen y'
en2 English AndreyPavlov 2022-08-01 18:03:48 1021
en1 English AndreyPavlov 2022-08-01 13:27:42 1025 Initial revision (saved to drafts)