This problem can be solved with an online convolution algorithm called Relaxed Convolution.

[1] Tutorial of Relaxed Convolution

Relaxed Convolution is an algorithm that solves the following problem in a total of \(O(N (\log N)^2)\) time.

• Let \(A\) and \(B\) polynomials, \(a_n \coloneqq[x^n]A, b_n \coloneqq[x^n]B\), and \(c_n \coloneqq [x^n]AB\). (Initially, \(A\) and \(B\) are unknown.)
• Process the following query online for each \(i = 0,1,2, \ldots, N\):
  • given \(a_i\) and \(b_i\), find \(c_i\).

Take the minimum positive integer \(M\) with \(2^M - 2 \geq N\); then \(2^M-2 = O(N)\). For simplicity, we replace \(N\) with \(2^M-2\) to assume that \(N = 2^M - 2\).

We manage \(F_{p,q} \coloneqq (\displaystyle\sum_{i=q2^p-1}^{(q+1)2^p-2} A_ix^i)(\displaystyle\sum_{i=2^p-1}^{2^{p+1}-2} B_ix^i)\)
and \(G_{p,q} \coloneqq (\displaystyle\sum_{i=2^p-1}^{2^{p+1}-2} A_ix^i)(\displaystyle\sum_{i=q2^p-1}^{(q+1)2^p-2} B_ix^i)\)

for all integer pairs \((p,q)\) such that \(0 \leq p < M\) and \(1 \leq q < 2^{(M-p)}\).

Then, \(AB = \displaystyle\sum_{p=0}^{M - 1}\sum_{q=1}^{2^{(M-p)} - 1} F_{p,q} +\displaystyle\sum_{p=0}^{M - 1}\sum_{q=2}^{2^{(M-p)} - 1} G_{p,q}\).

We compute \(F_{p,q}\) and \(G_{p,q}\) once the value is determined; i.e. when the query with \(i = (q+1)2^p-2\) is given. Since the coefficients of the \(((q+1) 2^p-3)\)-th and lower degrees of \(F_{p,q}\) and \(G_{p,q}\) are all \(0\), it is sufficient to compute \(((q+1) 2^p-2)\)-th and higher degrees; this is essentially a product of polynomials of \(2^p\)-th degree, so the polynomials in the form of \(F_{p,*}\) and \(G_{p,*}\) can be found in a total of \(O(p2^M)\) time, for a total of \(O(M^22^M) = O(N(\log N)^2)\) time to compute all \(F_{p,q}\) and \(G_{p,q}\).
The response to the query can be found as the sum of \(O(\log N)\) terms of \(F_{p,q}\) and \(G_{p,q}\), since there are at most two \(q\)s such that \((q+1)2^p-2 \leq i \leq (q+3)2^p-4\) for each \(i\) and \(p\) (note that all \(F_{p,q}\) and \(G_{p,q}\) are already computed at each point), which can be processed in a total of \(O(N\log N)\) time. As a whole, the queries can be processed in a total of \(O(N (\log N)^2)\) time.

[2] Solution of this problem

Let \(F = \sum F_nx^n\) and \(G_n \coloneqq [x^n]F^2\); then \(F_n = A_n(\displaystyle\sum_{i<n} G_i)\).
With Relaxed Convolution, one can find \(G_n\) from the values of \(F_n\); also, one can manage the cumulative sums of \(G_i\) to find \(F_{n+1}\) from the values of \(G_n\) in an \(O(1)\) time. In total, \(F_1,F_2, \ldots\), and \(F_N\) have been found in an \(O(N(\log N)^2)\) time.