I myself have been quite interested in FFT, power series and gfology in competitive programming since about a year ago (I'm not good at these topics at all, though). Here are some of my thoughs about the problem.

For the general function $$$F(n, k)$$$, (i. e., an array consisting of $$$\frac{1}{2}n(n+1)$$$ values), there definitely cannot be an $$$\text{o}(n^2)$$$ solution as the size of the input is already $$$\text{O}(n^2)$$$ without any useless information(all those values have an influence on the output). If you want a solution in which $$$F(n, k)$$$ is a fixed function given at the beginning of the input and $$$\text{O}(\text{poly}(n))$$$ queries are made afterwards, it's hardly possible to do each query in $$$\text{O}(n \log n)$$$ either, because the problem is at least as hard as matrix multiplication(with $$$h_i = 1$$$).

For specific functions $$$F(n, k)$$$, I also don't think a general solution exists — if there was a solution it should also be able to solve the general problem mentioned in the previous paragraph. In this case, you can only deal with particular situations: for instance, when $$$F(n, k)$$$ can be represented as $$$a_nb_kc_{n-k}$$$ with three fixed arrays $$$a$$$, $$$b$$$, $$$c$$$, a simple convolution will solve anything. However, when $$$F(n, k)$$$ becomes $$$k^n$$$ or stirling numbers of the second kind (in my opinion these two are probably as difficult), the problem quickly becomes much more unsolvable: the simplest case where $$$h_i = 1$$$ is already equivalent to a multipoint evalution on an algebraic sequence $$$1, 2, ..., n$$$, which currently has only an $$$\text{O}(n \log^2 n)$$$ solution and is much more complicated than convolution. The case $$$h_i \not= 1$$$ is too hard — I guess there doesn't exist a solution with complexity $$$\text{O}(n \text{polylog}(n))$$$, and I'm pretty sure it's impossible using only techniques currently introduced into competitive programming combined with elementary algebra transformations.