themaskedhero's blog

Sum of Squares Problem
By themaskedhero, history, 9 years ago, In English

Hi all,

Today I was working on this problem. I recognize that this is a data structure problem, but I am curious on how to solve it with:

  1. Segtree + lazy propagation and 2.Binary indexed tree

Thank you much in advance!

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

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

Just make a segment tree such that each node contains the sum of squres of numbers in its range and the sum of the numbers. For the first update what we are doing for each range while updating in fact is: (a[l]+c)^2 + (a[l+1]+c)^2.....(a[r]+c)^2 so since (a+b)^2=a^2 + 2ab + b^2 Then the last sum is equal to : (sum of the squres of current numbers of the range)+(2*c*(sum of current numbers of the range))+((r-l+1)*(c^2)) Where c is the number that we are increasing the interval by. The second update query is easy. And of course sum query is easy since we could do the update.

→ Reply