CSES Subtree Queries

You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,…,n, and node 1 is the root. Each node has a value.

Your task is to process following types of queries:

1. change the value of node s to x

2. calculate the sum of values in the subtree of node s

Constraints

$1\le n, q \le 2 \cdot 10^5$
$1≤a,b,s≤n$

$1≤v_i,x≤10^9$

Naive approaches:

1. Store tree nodes in a hash table and sum of each nodes in a vector:

Update time complexity: $O(n)$

After updating tree nodes value in the hash table, it needs to recalculate the sum vector.

Calculate sum of subtree time complexity: $O(1)$

Direct access on the sum vector.

2. Store tree nodes in a hash table and calculate subtree sum with BFS/DFS approach:

Update time complexity: $O(1)$

Direct access on the hash table.

Calculate sum of subtree time complexity: $O(n)$

Calculate subtree sum with BFS/DFS. If the tree structure is worse, it may occurs $n$ operations.

Segment Tree approach:

Update and calculate sum of subtree time complexity with both $O(1og(n))$

The following example will take tree size = $n$ as a power of 2 here for simplicity. It can be generalized to arbitrary tree size.

Transform the above tree to depth first search order, so that it can perform a range sum queries and construct a segment tree.

Original Order = $\{n_0, n_1, n_2, n_3, n_4, n_5, n_6, n_7\}$

DFS order = $\{n_0, n_1, n_3, n_4, n_2, n_5, n_7, n_6\}$

Also remember to store the subtree size of each node.

Subtree size = $\{8,3,1,1,4,2,1,1\}$ (DFS order)

$O2D(x) = y$ Transfers original order to DFS order

$D2O(y) = x$ Transfers original order to Original order

For example, $O2D(2) = 4$

Then, calculate the sum of subtree $n_2$

$SumOf(n_2) = RangeSum(O2D(2), O2D(2)+SubTreeSize[O2D(2)]))$

That is DFS index $[4, 4+4) = [4,8)$

$ = sum(\{ n_2, n_5, n_7, n_6\})$

As a result, we can obtain a range query to perform a segment tree sum.

Then, we want to create a binary segment tree with following structure:

Tree = ${v_0, v_1, v_3, v_4, v_5, v_6, v_7}$ (DFS order value)

In order to obtain the range sum $[start, end)$ (start and end are both in dfs order), we can implement the following steps:

1. Start and end add $n$. Shift them to the most bottom layer.
2. If start index is odd, add current index value in the segment tree. Then, increase start index by 1.
3. If end index is odd, decrease the end index first. Then, add current index value in the segment tree.
4. Both indices divided by 2. (Move to next layer)
5. Repeat step 2 to 4, until start index is larger than or equal to end index.
6. The cumulative result is the range sum.

For example, $RangeSum(4, 7)$:

1. Add total size $n=8$. Start = 12, end = 15.
2. End index = 15 is odd. Decrease end index by 1 and add index 14 value to sum.
3. Divide both indices by 2.
4. Start = 6, end = 7. Decrease end index by 1 and add index 6 value to sum.
5. Divide both indices by 2.
6. Start = end = 3. End of loop.
7. The result of sum from index 6 [4,6) + index 14 [6], which is correct.

Even if, total size $n$ is not power of 2. The above algorithm still works.

CSES Subtree Queries