Graph Theory37 sections · 1633 units
Open in Course

Chain Positions

(Indexing nodes within chains)

Within each chain, assign positions from top to bottom. Let pos[v] be the position of node vv in its chain, starting from 00. The topmost node in a chain has pos=0pos = 0. As you DFS, maintain a counter chain_pos[c] for each chain cc. When you visit node vv in chain cc, set pos[v] = chain_pos[c] and increment chain_pos[c].

Now each node has two coordinates: which chain it is in via chain[v], and where in that chain via pos[v]. This lets you map tree nodes to segment tree indices.