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≤n,q≤2⋅105
1≤a,b,s≤n
1≤a,b,s≤n
1≤vi,x≤109
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 = {n0,n1,n2,n3,n4,n5,n6,n7}
DFS order = {n0,n1,n3,n4,n2,n5,n7,n6}
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 n2
SumOf(n2)=RangeSum(O2D(2),O2D(2)+SubTreeSize[O2D(2)]))
=sum({n2,n5,n7,n6})
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 = v0,v1,v3,v4,v5,v6,v7 (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:
- Start and end add n. Shift them to the most bottom layer.
- If start index is odd, add current index value in the segment tree. Then, increase start index by 1.
- If end index is odd, decrease the end index first. Then, add current index value in the segment tree.
- Both indices divided by 2. (Move to next layer)
- Repeat step 2 to 4, until start index is larger than or equal to end index.
- The cumulative result is the range sum.
For example, RangeSum(4,7):
- Add total size n=8. Start = 12, end = 15.
- End index = 15 is odd. Decrease end index by 1 and add index 14 value to sum.
- Divide both indices by 2.
- Start = 6, end = 7. Decrease end index by 1 and add index 6 value to sum.
- Divide both indices by 2.
- Start = end = 3. End of loop.
- 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.
No comments:
Post a Comment