PROBLEM LINK:
Author: Anudeep Nekkanti and Praveen Dhinwa
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
easy-medium
PREREQUISITES:
data structures, tree
PROBLEM:
Given a rooted tree consists of n nodes rooted at node 1. Each node has a value associated with it, which is 0 initially.
You have to support the following Q operations on the tree.
Update x, y.
- Add 2^y to node x.
- Add 2^{y - d} in the nodes in the subtree of x which are at a distance of d.
- Add 2^{y - d} in the nodes in the ancestor nodes of x which are at a distance of d.
Query: Output the value at the node x modulo 10^9 + 7.
It’s guaranteed that y \leq 60.
SOLUTION
The update in the ancestor nodes of x can be done by going over all the y ancestors of x manually and updating the respective value at the nodes. Let value be the array which stores the value of the node. We can directly update value array of the ancestor nodes of x (including x) by going through them one by one.
Now, let us see how to handle the update of 2^{y - d} (d \geq 1) in the nodes in the subtree of x at at distance of d. There can be a lot of such vertices, updating them one by one can take worst case \mathcal{O}(n) time. But, instead of updating all the subtree nodes at a distance \leq y, we can do lazy updates.
At each node, we maintain a 60 lazy values. Let lazy[x][d] denote that sum of lazy values that should be updated in the node in the subtree of x and is at a distance of d.
When updating a node x with value y, we go over each d from 1 to y, and increase the lazy[x][d] by 2^{y - d}.
When answering a query at node x, we go through at max 60 ancestors of x and add the value of lazy[x][d] to our answer.
Psuedo Code
int value[MAXN]
int lazy[MAXN][63]
int pw2[MAXN]// pw2[i] denotes 2^i
void update(int x, int y) {
int py = y, px = x;
while (px > 0 && py >= 0) {
value[px] += pw2[py];
px = pr[px];
py --;
}
for (int d = 1; d <= y; ++d) {
lazy[x][d] += pw2[y - d];
}
}
int query(int x) {
int ans = value[x];
int px = parent[x], d = 1;
while (px > 0 && d <= 60) {
add(ans, lazy[px][d]);
px = parent[px];
d ++;
}
return ans
}
This way, the entire algorithm works in \mathcal{O}(60) per query and \mathcal{O}(60) per update.
The overall time complexity of the algorithm will be \mathcal{O}(60 * (Q + N)). Space complexity is \mathcal{O}(60 * N).