### tom's blog

By tom, history, 3 years ago,

Hello everyone,

I would like to quickly compute maximum sum subarray with queries (change ith element to x). Can we do it faster than O(log(n)) per query?

• +11

 » 3 years ago, # | ← Rev. 2 →   +5 UPD:I am sorry I misread the question
•  » » 3 years ago, # ^ |   0 How is this faster than log n?
 » 3 years ago, # |   +31 The answer is no, and here is the reasoning. You can answer this question using some logic by reducing the problem to a known one.If your initial array is a1, a2, ... an — you can replace it with [a1, -a1, a2, -a2, ... ]. Notice that when you query a range, it is the same as querying maximum value of ai in the range. Updates remain the same.If you suppose can do your problem in faster than log(n), then you can do this in faster than log(n), which is at this point in time, obviously impossible (otherwise segment trees would be sub-optimal).
•  » » 3 years ago, # ^ |   +36 Using your transition to "maximum value in the range" problem, one can also pick a different reasoning: if you can solve it faster than log(n), you can sort array faster than n * log(n) — just pick maximum element and replace it with  - INF n times.