secomo's blog

exploring segment tree
By secomo, history, 4 years ago, In English

hey... so I am learning about segment tree and I am wondring if It can solve this proplem that I came up with : given an array and some queries each query is a segment from index L to index R and the answer to the query is a[l]*1 + a[l+1]*2 + a[l+2]*3 +.... a[r]*(r-l+1) Is it possible to solve this proplem using segment tree and how? I am happy to see your opinions about this. Thank you for reading.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be solved with prefix sums if i recall correctly. It is also solvable with segtrees too. But i cant explain the solution.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

query = $$$\displaystyle\sum\limits_{i=l}^r a[i]*(i-l+1)$$$.

compute $$$\displaystyle\sum\limits_{i=l}^r( a[i]*i - a[i]*(l-1)$$$)

sum1 = $$$\displaystyle\sum\limits_{i=l}^r a[i]*i$$$

sum2 = $$$\displaystyle\sum\limits_{i=l}^r a[i]*(l-1)$$$

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can check these problems for adding arithmetic progression with a segment tree

https://cses.fi/problemset/task/1736

https://codeforces.net/edu/course/2/lesson/5/4/practice/contest/280801/problem/B

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you those are really interesting

    → Reply