Editing Heavy-light decomposition
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 45: | Line 45: | ||
In the above, <code>color(u,v)</code> represents the color (heavy or light) of the edge from <code>u</code> to <code>v</code>, <code>parent(v)</code> represents the parent of a node <code>v</code>, and <code>skip(v)</code> represents the parent of the highest (''i.e.'', least deep) node that is located on the same heavy path as node <code>v</code>. (It is so named because it allows us to "skip" through heavy paths.) In order for the latter to be implemented efficiently, every node whose parent link is heavy must be augmented with a pointer to the result of the <code>skip</code> function, but that is trivial to achieve. | In the above, <code>color(u,v)</code> represents the color (heavy or light) of the edge from <code>u</code> to <code>v</code>, <code>parent(v)</code> represents the parent of a node <code>v</code>, and <code>skip(v)</code> represents the parent of the highest (''i.e.'', least deep) node that is located on the same heavy path as node <code>v</code>. (It is so named because it allows us to "skip" through heavy paths.) In order for the latter to be implemented efficiently, every node whose parent link is heavy must be augmented with a pointer to the result of the <code>skip</code> function, but that is trivial to achieve. | ||
− | What is the running time of this fragment of code? There are | + | What is the running time of this fragment of code? There are most a logarithmic number of light edges on the path, each of which takes constant time to traverse. There are also at most a logarithmic number of heavy subpaths, since between each pair of adjacent heavy paths lies a light path. We spend at most a constant amount of time on each of these, so overall this "skipping" operation runs in logarithmic time. |
This might not seem like much, but let's see how it can be used to solve a simple problem. | This might not seem like much, but let's see how it can be used to solve a simple problem. |