1

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.

li yixiao
  • 59
  • 4
  • There is a nice O(log N)/operation solution if B contains the Fibonacci sequence like it does in the link. Do you want to modify the question? – Matt Timmermans Dec 17 '21 at 14:24
  • @ Matt Timmermans The link has an O(log n) solution because the sum of two fibonacci sequences starting from a1,b1 and a2,b2 is equal to a fibonacci sequence starting from (a1+b1, a2+b2), and two lazy combination tags can be combined as one. So do you have any idea about my question? – li yixiao Dec 18 '21 at 02:55
  • With an arbitrary sequence in B, your push-down idea takes O(n^2) time in the number of operations. I don't know a way to get that down to O(n log n). – Matt Timmermans Dec 18 '21 at 15:13

0 Answers0