Hello!

I've recently read about persistent segment trees and I found some good resources on the internet. I then remembered a problem I've seen earlier, which is requires algorithm for the following task:

You're given an array A1, A2, A3, ... An (n <= 100000) and lets say that this array is in version 1. Then m <= 100000 queries follow. For each query, we create a new "version" of the array, which is copied from some previous version v, then we increment all elements in the range [l, r] in this new version. Then we must say what is the sum of the elements in the range [i, j] for the new version.

This problem clearly resembles persistent segment tree (sum of ranges). Problem is, changes made aren't linear(if we draw a diagram of the versions, it will be a tree). I think this can be done using the following algorithm (in C++). For representing nodes of segment tree, we create a structure with pointers for left and right and we use lazy propagation. In some array we keep references to the roots of all versions up to now. When we have to build the new version, we take the tree of the old version, we create a new root for the new version. As we do the first step (updating the range [l, r]) we just create new nodes when a modification is needed and reuse those from the old version if they are not used. The problem is, I think that this approach would give correct answer, but I'm not sure about complexity of the algorithm (I need O(nlog(n))). Can somebody tell me whether my idea would work and if yes, what complexity would it have? Thank you in advance. I'll also appreciate if there is some other, easier way to create non-linear persistent segment tree.