Heavy-Light Decomposition: Tree Path Queries
You have a tree with weighted nodes. You need to answer thousands of queries like ‘what’s the sum of values on the path from node A to node B?’ or ‘update node X’s value to Y.’ The naive approach…
Read more →