Editing Heavy-light decomposition

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 93: Line 93:
 
To solve this simpler problem of querying the distance from the root to a given node, we augment our walk procedure as follows: when following a light edge, simply add its distance to a running total; when following a heavy path, add all the distances along the edges traversed to the running total (as well as the distance along the light edge at the top, if any). The latter can be performed efficiently, along with modifications, if each heavy path is augmented with a data structure such as a [[segment tree]] or [[binary indexed tree]] (in which the individual array elements correspond to the weights of the edges of the heavy path).
 
To solve this simpler problem of querying the distance from the root to a given node, we augment our walk procedure as follows: when following a light edge, simply add its distance to a running total; when following a heavy path, add all the distances along the edges traversed to the running total (as well as the distance along the light edge at the top, if any). The latter can be performed efficiently, along with modifications, if each heavy path is augmented with a data structure such as a [[segment tree]] or [[binary indexed tree]] (in which the individual array elements correspond to the weights of the edges of the heavy path).
  
This gives <math>O(\log^2 n)</math> time for queries. It consists of two "skips" and a LCA query. In the "skips", we may have to ascend logarithmically many heavy paths each of which takes logarithmic time, and so we need <math>O(\log^2 n)</math> time. An update, merely an update to the underlying array structure, takes <math>O(\log n)</math> time.
+
This gives <math>O(\log n)</math> time for queries, since it consists of two "skips" and a LCA query, all of which take logarithmic time or better. It might seem that we have to ascend logarithmically many heavy paths each of which takes logarithmic time, but this is not the case; only the first one, if we start out on it, has to take logarithmic time to query; for the others, which we skip over in their entirety, we can just look up a variable indicating the sum of all weights on that path, which can be updated in constant time when any edge on that path is updated. An update, merely an update to the underlying array structure, takes <math>O(\log n)</math> time also.
  
 
==References==
 
==References==
 
* Wang, Hanson. (2009). Personal communication.
 
* Wang, Hanson. (2009). Personal communication.
 
* D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, ''in'' "Proc. Thirteenth Annual ACM Symp. on Theory of Computing," pp. 114–122, 1981.
 
* D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, ''in'' "Proc. Thirteenth Annual ACM Symp. on Theory of Computing," pp. 114–122, 1981.

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)