hehaodele's blog

By hehaodele, history, 2 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it