Hi everyone,
I am curious about whether the following interval problem can be solved by the interval tree or other efficient data-structures. Given an initial sequence $$$a_1,a_2,\cdots,a_n$$$. We have one type of modification parameterized by l,r,x,y (it is guareeted that r-l=y-x) meaning add the interval [l,r] to the interval [x,y]. More specifically, this operation will make every $$$a_i=a_i + a_{i-x+l}$$$ for $$$x \leq i \leq y$$$. We have one type of query which is ask the sum of the elements in a given interval [l,r].
Does anyone have any similar experience with this kind of problem?
There is a similar problem on CodeChef, where you are given two arrays $$$A$$$ and $$$B$$$. And queries are adding a prefix of $$$B$$$ to suffix of $$$A$$$. (In your description $$$l=1$$$ and $$$y=n$$$).
The idea is to consider $$$A$$$ and $$$B$$$ as polynomials. Then the updates become adding $$$x^{len}B(x)$$$ to $$$A(x)$$$. But this addition is costly, so when you get an update push it into a buffer. And after $$$O(\sqrt{Q\lg Q})$$$ updates in the buffer, you can take all the updates and apply them at once using one polynomial multiplication. And for sum queries, you can take sum from current $$$A$$$ and add the pending updates from buffer.