### secomo's blog

By secomo, history, 7 weeks ago,

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

 » 7 weeks ago, # |   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.
 » 7 weeks ago, # | ← 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)$
•  » » 7 weeks ago, # ^ |   0 Thanks you. that was very helpful
 » 7 weeks ago, # |   0 You can check these problems for adding arithmetic progression with a segment treehttps://cses.fi/problemset/task/1736https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/B
•  » » 7 weeks ago, # ^ |   0 thank you those are really interesting