Suppose there are two sequences A:a1,a2,...,an and B:b1,b2,...bn ,and we need two operations:
1.sum(i,j):calculate the sum of ai,a(i+1),...,aj
2.range_add(i,j):range modify the sequence A in [i,j] , with ai=ai+b1,a(i+1)=a(i+1)+b2,...,aj=aj+b(j-i+1)
Is it possible to make an operation O(log n) time ?
A simple lazy propagation tree seems could not save the problem, if you store the sum of the interval in the node, and use the first addend in sequence B to tag a lazy modified node, because when a modification is made on a node that is already tagged, you cannot simply combine the new change with the previous one, and you have to push the previous tag down, and if their children are also already tagged, then more pushes are needed, causing the total time comlexity O(n).
Maybe we could store all tags in an array, and push tags of current node to the back of its children's tag array, and I wonder is this algorithm O(log n) or O(n)? (It should be O(n) since my submit in codeforces failed, so I actually want to know how to calculate that time complexity)
https://codeforces.com/contest/446/problem/C That's where I got my question.