You are not logged in. Please login at www.codechef.com to post your questions!

×

FIBTREE - Editorial

3
1

Problem link : contest practice

Difficulty : Hard

Pre-requisites : heavy-light decomposition, segment trees, persistence

Solution :

First, let's recall one of the properties of Fibonacci numbers: the n-th Fibbonacci number is axn+(1-a)yn, where:

  • a equals to (3+sqrt(5))/(5+sqrt(5));
  • x equals to (1+sqrt(5))/2;
  • y equals to (1-sqrt(5))/2.

So, the sum of the first K Fibbonacci numbers is basically the sum of two progressions.

Now there are still two questions:

  1. How do we operate with floating point numbers? How do we avoid the precision loss?
  2. How do we add the geometric progression on a segment?

The answer to the first quesion is: we don't operate with floating point numbers/doubles at all. This can be achieved this way: since our modulo 1000000009 is a prime, we can find such integer T that its' square modulo 1000000009 is 5. This way we can define sqrt(5) in the modulo ring. Now we have that sqrt(5) is an integer, so all the operations become ordinary modular arithmetic operations.

Now we can have a segment tree for the progressions addition. Here is the tutorial on developing such kind of segment trees.

When we have a segment tree, it's time to make in persistent and to build the heavy-light decomposition of the tree. Pay attention that if you store all the chains of the HLD in the single segment tree, there is no more effort required to maintain the versions of the persistence correctly. But if not, you'll also have to store some persistent array to get access to the right version of some exact chain. Here is the detailed desription of persistent heavy-light decomposition's implementation.

Setter's solution: link

Tester's solution: link

This question is marked "community wiki".

asked 15 Sep '14, 15:37

xcwgf666's gravatar image

6★xcwgf666 ♦♦
709426276
accept rate: 0%

edited 15 Sep '14, 15:54

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156181

thanks for making good question ^_^

(16 Sep '14, 00:13) abcdexter243★

There is another easy way to update the Segment Tree with the Fibonacci series. Define a new sequence G such that G(1)=F(a)+F(b)+F(c)... for all a,b,c... such that a,b,c are all the starting terms of the sequence added. Similarly for G(2). Clearly G(3)=G(2)+G(1) (The Fibonacci relation still holds.) This can be used to generate the sequence using matrix exponentiation or precomputation.

link

answered 15 Sep '14, 17:57

patch_adams's gravatar image

5★patch_adams
16
accept rate: 0%

edited 15 Sep '14, 23:35

How do you answer to "sum over subtree" query in your solution? The way I know about requires one more segment tree, can you do it somehow easier?

link

answered 16 Sep '14, 21:10

mmaxio's gravatar image

7★mmaxio
81128
accept rate: 0%

It can be done in the same way. Maintain another attribute in the segment tree node where instead of a value of F(a) for a node, we will have F(a) + F(b) + F(c) + ...F(x) where x is the deepest node in the path, that the current node is a parent of. This can be expressed again in terms of Fibonacci numbers. Solve accordingly.

(16 Sep '14, 22:10) patch_adams5★

There are many other approaches for this problem.

link

answered 20 Sep '14, 14:01

shizhouxing's gravatar image

6★shizhouxing
1112
accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×10,064
×994
×702
×316
×61
×37
×24

Asked: 15 Sep '14, 15:37

Seen: 5,360 times

Last updated: 20 Sep '14, 14:01