I have an array $a_1, a_2, \dots, a_n$. After $O(n)$ preprocessing, I want to be able to compute each of the following in amortized $O(\log n)$:

  1. Given $l,r,b,d$, for each $i \in \{l,\ldots,r\}$, increase $a_i$ by $b + (i-l)d$.
  2. Given $l,r$, compute $\sum_{i=l}^r a_i$.
  • 1
    $\begingroup$ Where are all these contest-style questions coming from? $\endgroup$ – Yuval Filmus Apr 22 '20 at 17:50
  • $\begingroup$ What is the best solution you've found so far, and what running time does it have for each of those two operations? $\endgroup$ – D.W. Apr 22 '20 at 18:06
  • $\begingroup$ It seems to me that I almost solved the problem. I came up with storing a progression step and the first member of the progression at each vertex of the tree of segments. And when the request arrives, it’s easy to calculate the required amount. And when a request for a sub-segment is received regarding the first request, then I will push it to the descendants, counting q. But I'm not sure that I can build such a tree of segments in O (n). $\endgroup$ – Maxim Apr 22 '20 at 22:15

Hint: find a data structure that supports these three basic operations:

  1. Given $l,r,b$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $b$.
  2. Given $l,r,d$, for each $i \in \{l,\dots,r\}$, increase $a_i$ by $id$.
  3. Given $l,r$, compute $\sum_{i=l}^r a_i$.

You can then use those basic operations to implement your operation 1.

Can you think of any way to support basic operations 1+3? Can you think of any way to support basic operations 2+3? If you can answer both of those questions with a "yes", you will probably then be able to solve your problem.

  • $\begingroup$ I think, for operations 1+3 I can use default segment tree. For operations 2+3 i think for operations 2 + 3, I think I need to use a modified tree of segments: at the top of each subtree, I need to store the value by which I need to increase this sub-segment. $\endgroup$ – Maxim Apr 22 '20 at 18:58
  • $\begingroup$ Can you tell me how solving this subtask will help me solve the main problem? $\endgroup$ – Maxim Apr 22 '20 at 19:00
  • $\begingroup$ @Maxim, it's your task, so I suggest spending some more time thinking about it. I notice that you haven't responded to the other requests (about the source of this problem, or what attempts you've made), which makes it look like you're hoping someone will solve it for you. $\endgroup$ – D.W. Apr 22 '20 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.