Answers to: FIBTREE - Editorialhttps://discuss.codechef.com/questions/50952/fibtree-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/SEPT14/problems/FIBTREE/">contest</a> <a href="http://www.codechef.com/problems/FIBTREE/">practice</a></p>
<p><strong>Difficulty</strong> : Hard</p>
<p><strong>Pre-requisites</strong> : heavy-light decomposition, segment trees, persistence</p>
<p><strong>Solution</strong> : </p>
<p>First, let's recall one of the properties of Fibonacci numbers: the <strong>n</strong>-th Fibbonacci number is <strong>ax<sup>n</sup>+(1-a)y<sup>n</sup></strong>, where:</p>
<ul>
<li><strong>a</strong> equals to <strong>(3+sqrt(5))/(5+sqrt(5))</strong>;</li>
<li><strong>x</strong> equals to <strong>(1+sqrt(5))/2</strong>;</li>
<li><strong>y</strong> equals to <strong>(1-sqrt(5))/2</strong>.</li>
</ul>
<p>So, the sum of the first <strong>K</strong> Fibbonacci numbers is basically the sum of two progressions.</p>
<p>Now there are still two questions:</p>
<ol>
<li>How do we operate with floating point numbers? How do we avoid the precision loss?</li>
<li>How do we add the geometric progression on a segment?</li>
</ol>
<p>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 <strong>1000000009</strong> is a prime, we can find such integer <strong>T</strong> that its' square modulo <strong>1000000009</strong> is <strong>5</strong>. This way we can define <strong>sqrt(5)</strong> in the modulo ring. Now we have that <strong>sqrt(5)</strong> is an integer, so all the operations become ordinary modular arithmetic operations.</p>
<p>Now we can have a segment tree for the progressions addition. <a href="http://discuss.codechef.com/questions/42557/funagp-editorial">Here</a> is the tutorial on developing such kind of segment trees.</p>
<p>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. <a href="http://discuss.codechef.com/questions/6548/query-editorial">Here</a> is the detailed desription of persistent heavy-light decomposition's implementation.</p>
<p>Setter's solution: <a href="http://www.codechef.com/download/Solutions/2014/September/Setter/FIBTREE.cpp">link</a></p>
<p>Tester's solution: <a href="http://www.codechef.com/download/Solutions/2014/September/Tester/FIBTREE.cpp">link</a></p>enSat, 20 Sep 2014 14:01:58 +0530Answer by shizhouxinghttps://discuss.codechef.com/questions/50952/fibtree-editorial/51350<p>There are many other approaches for this problem.</p>shizhouxingSat, 20 Sep 2014 14:01:58 +0530https://discuss.codechef.com/questions/50952/fibtree-editorial/51350Answer by mmaxiohttps://discuss.codechef.com/questions/50952/fibtree-editorial/51153<p>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?</p>mmaxioTue, 16 Sep 2014 21:10:46 +0530https://discuss.codechef.com/questions/50952/fibtree-editorial/51153Answer by patch_adamshttps://discuss.codechef.com/questions/50952/fibtree-editorial/51001<p>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.</p>patch_adamsMon, 15 Sep 2014 17:57:59 +0530https://discuss.codechef.com/questions/50952/fibtree-editorial/51001