Tree (DFS visit order)
Flattened array — order[t] (node entered at time t)
flat[t] = value of order[t] (Fenwick is built over this)
tin / tout per node
timer: 0
current: -
nodes done: 0
subtree sum: -
Fenwick ops: 0
current node / tin
finished (tout set)
selected subtree range
Fenwick cell touched
Complexity
| Operation | Cost | How |
|---|---|---|
| Build flatten (DFS) | O(n) | one traversal, tin/tout |
| Subtree → range | O(1) | read [tin[v], tout[v]] |
| Subtree size | O(1) | tout[v] - tin[v] + 1 |
| Ancestor test | O(1) | interval containment |
| Subtree sum | O(log n) | Fenwick range query |
| Point update | O(log n) | Fenwick add at tin[v] |