Блог пользователя tom

Maximum sum subarray problem revisited
Автор tom, история, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

UPD:I am sorry I misread the question

→ Ответить
»
10 лет назад, скрыть # |
 
Проголосовать: нравится +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).

→ Ответить