Hello There I was reading this problem and i noticed that it could be solved with a persistent segment tree which hold multiple of children and every tree is based on the parent's tree
the problem is in this problem we have two types of queries... the second one being update
so i was wondering if updates on a persistent segment tree are possible in log(n) ?
the way i see it updating a certain tree means i have to update all the trees based on it which could lead to linear time...any opinions ??
You need to update only verticles on path from root to leave you need to change(because only this verticles will be changed). So it takes O(logn) time.
so you're saying that changing a node's value i only need to change this node's tree and all trees that are based on this tree don't need changing ?
The main idea is to change nodes that are really changed