# Heavy-Light Decomposition

Authors: Benjamin Qi, Andrew Cheng

Path and subtree updates and queries.

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution## Tutorial

Suppose that you want to support the following operations on a tree:

Update all nodes along the path from node $x$ to node $y$.

Find the sum, maximum, minimum (or any other operation that satisfies the associative property) along the path from node $x$ to node $y$.

Heavy Light Decomposition (or HLD) supports both operations efficiently.

### Definitions

- A
**heavy child**of a node is the child with the largest subtree size rooted at the child. - A
**light child**of a node is any child that is not a**heavy child**. - A
**heavy edge**connects a node to its**heavy child**. - A
**light edge**connects a node to any of its**light children**. - A
**heavy path**is the path formed by a collection**heavy edges**. - A
**light path**is the path formed by a collection**light edges**.

### Properties

**Any path from node $x$ to node $y$ on the tree can pass through at most
$\mathcal{O}(\log N)$ light edges.**

Proof

Since a heavy path can only be broken by a light edge (or else the edge will be a part of the heavy path), we can know that there are at most $\mathcal{O}(\log N)$ heavy paths on any path from an arbitrary node $x$ to an arbitrary node $y$.

In addition, by using segment trees (or any other RURQ data structure) we can calculate the value of any consecutive interval on any heavy path in $\mathcal{O}(\log N)$ time.

Since there are at most $\mathcal{O}(\log N)$ heavy paths and $\mathcal{O}(\log N)$ light edges, computing the value on the path from node $x$ to node $y$ will take $\mathcal{O}(\log^2 N + \log N)$ = $\mathcal{O}(\log^2 N)$ time. We can answer $Q$ queries in $\mathcal{O}(Q \log^2 N)$ time.

Here's a helpful animation of how the algorithm works:

We can solve the focus problem "Path Queries II" using Heavy Light Decomposition:

C++

#include "bits/stdc++.h"using namespace std;const int N = 2e5 + 5;const int D = 19;const int S = (1 << D);int n, q, v[N];vector<int> adj[N];

Resources | ||||
---|---|---|---|---|

cp-algo | For an alternate implementation, see below | |||

CF | blog + video for USACO Cowland. Binary jumping isn't necessary though. |

### Optional: Tree Queries in O(NQ)

This is why you don't set problems where $\Theta(Q\sqrt N\log N)$ is intended ...

## Implementations

Resources | ||||
---|---|---|---|---|

CF | ||||

CF | not complete | |||

Benq | complete implementation following the above two articles with minor modifications |

### This section is not complete.

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Gold | Easy | ## Show TagsHLD, PURS | |||

SPOJ | Easy | ## Show TagsHLD | |||

Gold | Normal | ## Show TagsHLD | |||

Platinum | Normal | ## Show TagsHLD | |||

HR | Normal | ## Show TagsHLD, RURQ | |||

Old Gold | Normal | ## Show TagsHLD, PURS | |||

YS | Normal | ## Show TagsHLD, SegTree | |||

CF | Hard | ## Show TagsHLD | |||

CF | Hard | ## Show TagsHLD | |||

TLX | Hard | ## Show TagsHLD | |||

JOI | Hard | ## Show TagsHLD | |||

JOI | Very Hard | ## Show TagsHLD |

### Warning!

"Grass Planting" isn't submittable on the USACO website. Use this link to submit.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!