Thursday, July 21, 2011

Some Problems based on segment trees.

Try this problem.

It's based on segment trees. Not difficult but may require optimization.


Now a bit difficult one.

You may stop reading below do it yourself.

Hint.
here different nodes are updated with different weights in a range.
Fortunately when querying the range, the sum is asked. And we have a trick here.

the idea is simple.
Mathematically sum of two parabolas is also a parabola.

(a1*x^2 + b1*x + c1) + (a2*x^2 + b2*x + c2) = (a1+a2) * x^2 + (b1+b2) * x + (c1+c2)
which is also a parabola.

let Q(x) = a * x^2 + b * x + c
suppose a parabola falls in range (x1,x2)
the sum is
Q(x1) + Q(x1+1) + Q(x1+2) ... Q(x2)
= a * (x1^2 + (x1+1) ^2 + (x1+2) ^2 .... x2^2 )
+ b * ( x1 + x1+1 + x1+2 ... x2 ) + c * (x2-x1+1)


Store 4 things in each node.
3 coefficients of the parabolas and 1 sum of the blocks in the range the node covers.


A difficult one



Enjoy!!


1 comment: