A special interval modification and query problem

Revision en1, by hehaodele, 2020-06-09 23:17:36

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?

Tags #segment tree, #interval, #advance data structures, #basic math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hehaodele 2020-06-09 23:17:36 651 Initial revision (published)