Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 63 ยท Practice and Review

CSES Range Query and Tree Problems Walkthrough

A walkthrough of CSES range query and tree problems with original Python: segment tree descent, offline Fenwick, binary lifting, Euler tour path sums, path counting and centroids.

Two sections of the CSES Problem Set go together: Range Queries (about 20 problems) and Tree Algorithms (about 25). The first teaches how to keep an array queryable while it changes. The second teaches how to flatten, root, lift and decompose trees. Many of the hardest problems combine both, which is why they are covered together here.

This lesson explains the idea of eight representative problems, with original Python tested against naive solutions. The statements are my own short paraphrases, so read the originals on the CSES site and solve them first. Background: Fenwick and Segment Trees for Contests, Prefix Sums and Difference Arrays and Trees, Diameters and LCA.

flowchart TD
    Q["Range or tree query"] --> U{"Do values change?"}
    U -- "no" --> P["Prefix sums, sparse table, offline sorting"]
    U -- "yes" --> F["Fenwick tree or segment tree"]
    Q --> T{"Is there a tree?"}
    T -- "subtree question" --> E["Euler tour turns it into a range"]
    T -- "root path or ancestors" --> L["Binary lifting, or Euler + Fenwick"]
    T -- "all paths" --> C["Centroid decomposition"]

The first question is always whether the data changes; the second is whether there is a tree to flatten.

Range queries: descent and offline compression

The easy problems here are direct uses of structures you know: static range sum and XOR (prefix arrays), static range minimum (sparse table), dynamic range sum (Fenwick tree) and range minimum with updates (segment tree). The interesting ones need a twist.

Hotel Queries. Hotels have free rooms, groups arrive one by one, and each group takes the leftmost hotel with at least as many free rooms as it needs, then that hotel loses those rooms. Naively each group scans the hotels. Instead keep a segment tree of maxima over the hotels. To find the leftmost hotel with value at least x: if the root's maximum is below x, answer none; otherwise walk down from the root, going to the left child whenever its maximum is at least x, else to the right. That one root-to-leaf walk is segment tree descent, O(log n) with no range query at all. Then update the leaf. The same trick finds "first position where the prefix sum reaches k" or "first element at least x after position p" (with a small extension).

Salary Queries. Employees have salaries; updates change one employee's salary; queries ask how many salaries lie in [a, b]. Values go up to 10^9, so index a Fenwick tree by salary is impossible, but a fully offline solution compresses them: read all queries first, collect every salary that will ever exist (initial and updated), sort and number them, then use a Fenwick tree of counts over those ranks. Each update removes one count and adds one; each query is a difference of two prefix counts, found with bisect. This is the standard cure for large coordinates when you may read the input first, see Offline Queries.

Python Hotel queries by tree descent, and salary queries offline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trees: kth ancestors, root-path sums and path counting

The tree problems share a toolkit: root the tree, get an iterative traversal order, then choose between binary lifting (jump up), an Euler tour (subtrees as ranges) and difference sums (path updates).

Company Queries I/II. A company hierarchy is a tree. Query I asks for the k-th boss of an employee; query II asks for the lowest common boss of two employees. Both are binary lifting: up[b][v] is the 2^b-th ancestor; the k-th ancestor applies the bits of k; the LCA equalizes the depths, then jumps both nodes up from the highest bit down while their ancestors differ.

Path Queries. Each node has a value; updates change one node's value; queries ask for the sum along the path from the root to a node v. The sum on the root path of v includes node u exactly when u is an ancestor of v, that is when v lies in the Euler range of u. So changing node u by d means adding d to every position in u's Euler range, and a query reads one point. A Fenwick tree over a difference array does range add and point query in O(log n). This is the central trick that lets one flat array answer many tree questions.

Counting Paths. Given many paths (a, b), count for every node how many paths pass through it. Add +1 at a and at b, subtract 1 at c = lca(a, b) and 1 at the parent of c; then sweep the tree from the leaves to the root, adding each node's total to its parent. The subtree total at v is then exactly the number of paths through v. This is the tree version of the difference array from prefix sums.

Python Kth ancestors, Euler-tour path sums and path counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Distances and centroids

Tree Distances I. For every node, how far is the farthest node? The farthest node from any vertex is always one of the two endpoints of a diameter, so find the endpoints a and b with two BFS runs and answer max(dist(v, a), dist(v, b)) using two more BFS runs. (Tree Distances II, the sum of distances to all nodes, is rerooting, covered in Trees, Diameters and LCA.)

Finding a Centroid. Print a node whose removal leaves only components of at most n / 2 nodes. Compute subtree sizes with a rooted traversal; start at the root and keep moving into a child whose subtree is more than half the tree; the vertex where you stop is a centroid. This is the first step of the centroid decomposition.

Fixed-Length Paths I and II. Count paths with exactly k edges (I) or between k1 and k2 edges (II). These are the textbook uses of centroid decomposition. The full implementation, with a frequency array for the exact-length version and sorting for the range version, is in Centroid Decomposition for Contests. For range lengths, replace "equal to k" by "count of earlier distances between k1 - d and k2 - d", using a prefix-sum array over distances.

Python Tree distances and centroid finding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The other problems in these sections

  • Range Queries: Static Range Sum/Minimum, Range Xor Queries, Forest Queries (2D prefix sums), Dynamic Range Sum/Minimum: direct uses of prefix arrays, sparse tables, Fenwick and segment trees. Range Update Queries is a Fenwick tree over differences. List Removals is "find the k-th remaining element", solved with a Fenwick descent or the order-statistics idea in PBDS and C++ STL Tricks. Prefix Sum Queries and Pizzeria Queries store extra values in each segment tree node (sum and best prefix; two lazy minima).
  • Trees: Subordinates (subtree sizes), Tree Diameter, Tree Matching (greedy from the leaves up), Distance Queries (depth[u] + depth[v] - 2 * depth[lca]), Subtree Queries (Euler range plus Fenwick tree), Distinct Colors (offline Euler range with last-occurrence tricks), Path Queries II (heavy-light decomposition).
  • Visible Buildings Queries and Range Interval Queries are hard offline problems that combine sorting with a Fenwick or segment tree.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the segment tree descent find the leftmost hotel with at least x free rooms?

    Each node stores the maximum of its range, so the walk always knows whether the left half contains a suitable hotel.
  2. 2. Why does Salary Queries need offline coordinate compression?

    Reading all queries first lets you rank only the values that will ever be present, keeping the tree small.
  3. 3. How does the Path Queries solution update the sum on root paths when node u changes by d?

    The root path of v contains u iff v is in the subtree of u, which is the contiguous Euler range [tin[u], tout[u]).
  4. 4. In Counting Paths, why subtract 1 at both lca(a, b) and the parent of the lca?

    The subtree sums include +2 from the endpoints; the -1 at the lca leaves +1 on the lca, and the -1 at its parent cancels the remaining +1 above.

Summary

  • Segment tree descent finds the first position satisfying a condition on maxima in one O(log n) walk.
  • If you may read all queries first, compress the values and use a Fenwick tree over ranks.
  • Binary lifting answers k-th ancestor and LCA queries; an Euler tour with a Fenwick tree handles subtree updates and root-path sums.
  • Path counting uses a difference array on the tree, +1 at endpoints and -1 at the LCA and its parent, then a bottom-up sum.
  • The farthest vertex from any vertex is a diameter endpoint; a centroid is found by walking towards heavy children.

Next: CSES Math, String and Geometry Walkthrough