Блог пользователя secomo

exploring segment tree
Автор secomo, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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)$$$

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить