Normally a segment tree can perform the following operations:
- Update some index
- Range Query
Now, we will introduce more operations:
- Find a range sum for the array from K queries ago
- Create a copy of the array from K copies ago and update some index of it
Naively creating copies of our segment tree will result in both high time complexity and memory complexity. Hence, we need to find a smarter way to make copies.