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

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

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

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

UPD:I am sorry I misread the question

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

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

    → Ответить