Hello everyone,

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

# | User | Rating |
---|---|---|

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 206 |

2 | Monogon | 195 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 185 |

6 | vovuh | 184 |

7 | Ashishgup | 182 |

8 | Um_nik | 181 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

Hello everyone,

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2020 14:53:07 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

UPD:I am sorry I misread the question

How is this faster than log n?

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).

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 thann*log(n) — just pick maximum element and replace it with -INFntimes.