I have an already made a persistence segment tree but now there is a range update from some index to some index. How to update the persistence segment tree with less complexity? I am just rebuilding the persistence segment tree
3
votes
You should not be rebuilding of the whole tree. Talking of index are you implying that what you have is a list rather than a tree? Some (pseudo) code would be useful too.
- diginoise
Lets say I have an array of 3 2 4 1 5. Now I have to find the largest number from index 2 to index 4 of this array.By index I mean index of this array. l'd first make a persistence seg tree and then answer the queries. But now lets say that the original array elements are updated from 1 to 3. Now the array elements are 3 6 2 4 5. Now same query is again asked. So should I rebuild the whole persistence segment tree.
- Souravirus
1 Answers
1
votes
But now lets say that the original array elements are updated from 1 to 3. Now the array elements are 3 6 2 4 5. Now same query is again asked. So should I rebuild the whole persistence segment tree.
If a range update implies changing each element in the range in a non-formulaic way, then your best option is to apply a single-element update to each element in the given range. This will be O(range_sz * log n), where n is the number of elements in the tree.
I assume you know how to perform a single-element update in O(log n), if not please ask.
If however your update is more restricted, such as "set all elements in the range to the given value v", then you can use lazy updates: for every node in the segment tree whose associated range is included in the update range, set some custom field to the value v. Then, when querying, whenever you accept a node's range (if its range is included in your query range), check this field and, if it has a value, take that value as the min / max or whatever you're querying for.
This will keep both updates and queries at O(log n).
