I'm trying to solve a problem !
I have a tree. Plants with N nodes (N <= 100000).
For any node, the node level 1 is the direct child node and child node level K (K> 1) that all child nodes of the node level 1 level (K-1).
Initially, all nodes have the value 0
I have two queries:
1 u k e: all child note lever k of note u should be increased by e.
2 u: note u how much value.
input:
The first line contains the number N
N-1 line followed by the pair (u, v), v is the node level 1 of u
The next line contains the number of queries M (M <= 500000).
M line followed by queries.
output:
- results for each query 2.
Example
input:
6
1 2
1 3
2 4
3 5
3 6
6
2 6
1 1 2 1000
1 2 1 100
1 3 1 -100
2 4
2 5
output:
0
1100
900
Any ideal to solve it?
Thanks in advance.
(sorry if my English bad)
Don't you have a link to the problem? It is difficult to understand the text...
I think simple segment tree <+, sum> is enough. Put vertexes in level-order (first vertexes on 1st level, then from 2nd level, etc.). Note, that for every query one, affected vertexes make contiguous interval.
That's right, but only as long as nodes with the same level are ordered by the pre-order traversal ID, so that the sub-tree of a given level for any node form a contiguous segment.
A CHALLENGE: At first I had misunderstood the problem statement and thought the "type 2" query was "Sum of all nodes of sub-tree rooted at u". In case that was the "type 2" query, what would the solution be? I can't think of anything, because the nodes order necessary for "type 1" queries is not good for "type 2", that requires ALL descendants of node u. Anyone has something in mind for that "slight" modification?
You can use heavy-light decomposition. For each chain you need also segment tree <+, sum>. Query 1: Go through every chain from u and lower and add e to right nodes. Query 2: Sum of all nodes' values in chains which parent u is and <position u, last> in u's chain. Every query in O(log2n)
I'd like to add that since we're dealing with range updates / point queries, a BIT would be the ideal data structure (it's easier to code and it performs faster).
My rule of thumb for this is...
I used a binary search to find the affected interval, and then a BIT to update/query, so the whole complexity is O(Mlog2(n)), and of course it's too slow. Is there anyway to do this in O(Mlogn) ?
How do you used a binary search to find affected interval ? thank you :D (sorry for my bad english)
Since I cannot explain because of my poor English, I think I should show you my code:
Why is O(Mlog2(n)) too slow? M = 500000 and N = 100000, so that would be around 150M operations. What's the time limit?
150M operations could be TLE on Cube cluster with time limit 2s. So I don't think it can run well in 5s on Pyramid :P
Btw, is there any solution in O(MlogN) ?
Whatever the time limit, searching for the interval with binary search and then querying the Segment Tree for the value of that interval is NOT O(Mlog2(n)), since you're not doing a logarithmic query within the binary search, but rather just two successive logarithmic operations (binary search, then tree query). This makes the algorithm O(Mlog(n)).
Oh sorry, I forgot to say that my kthParent() function is O(logn) :P Is there anyway to reduce this to O(1) ?
Ooohhh, I see...
Yes, there's a way. What does your kthParent() function do? What I'd do for this problem is have a pair < int, int > array where the first value is the depth of the nodes and the second value is the pre-order ID. Then, suppose we need to update node u at depth k, and that node's subtree goes from ID a to ID b. What we need to do is lower – bound(k, a) and upper – bound(k, b) on that array to find the interval to update. You need to subtract 1 from upper – bound(k, b) as it turns out.