I use this post to try and explain an alternative to HLD that I have been using for more than a couple of months.
As many of you might be familiar HLD is a very tough thing to implement and is time-taking and must be implemented carefully.
Also if HLD sums are asked in short contests then it is going to be difficult to implement. Hence I came up with this technique.
I will try and explain this concept with the july long contest problem.
In this problem the value of number of nodes is given to be 10^5 which means maximum depth of the tree is 10^5 (worst case).
What I do is I perform a dfs in the tree and for every node whose depth%1000=1, I store the values of all its ancestors.
In worst case the memory complexity is (1000+2000+…10^5)= 1000(1+2+3+…+100) = 5*10^6.
After this I sort all these values and take a prefix xor.
Now for each query I have to travel up atmost 1000 ancestors and arrive at an ancestor whose depth%1000=1 and from there we can find xor of all elements less than k.
We do this for both nodes U and V(source and destination).
Because of the property of XOR all the values of the ancestors are canceled out.
Hence each query is (1000*Q) in the worst case.
Though this is somewhat testing the upper limits we can actually dynamically change the value in which we store the ancestors(1000 in this case). However this has not been required so far for me.
This is because we such situations(which test upper limits) rarely occur but even for that depending on the tree we can change the depth value.
Another question I solved using this techique is GPD in codechef.
GPD can also be solved using persistent trie but this method is far more easier.
My solutions for : PSHTTR
: GPD
In case for sum of values in the path between 2 nodes we can store sum of ancestors and we can find answer by:
sum upto U + sum upto V — sum upto LCA(U,V)
Upd1: If the maximum depth of tree is less than 1000 you can directly climb up the tree and do the calculations.
There can be cases where there are 10^5-1000 nodes which have depth%1000=1. For overcoming this we can have an initial dfs that has a count of depth%1000=1,2,3,4,…,999 and we can choose values which satisfy the memory limit using count(This is the dynamic change of value I mentioned).Also I believe we can strech upto depth%2000.
Note: I have not tried implementing this technique of changing node depth of storing values dynamically.
Upd2: Possible proof that this technique will not exceed memory limit if the depth is choosen according to Upd1 suggested by abx_2109 (thank you very much for the proof):
Proof : Let freq[i] store the number of nodes with value i=(depth%1000). Note that i takes value from 0 to 999. Also note that it covers all the nodes of the tree.Also if we take the minimum of all these 1000 values of freq[i], the minimum value <= 100 (approx).Because in the worst case we can have 100 nodes at each level.
