### Lain's blog

By Lain, history, 2 years ago,

Consider the $n$ degree polynomial $P(x) = \sum_{i=0}^n p_ix^i$. I call the polynomial $Q(x)$ it's "prefix sum polynomial" if it satisfies the following condition:

$Q(x) = \sum_{y=0}^x P(y)$

Essentially, $Q(x)$ is a prefix sum on the values of $P(x)$. So,

\begin{align} Q(x) &= \sum_{y=0}^x P(y) \\ &= \sum_{y=0}^x \sum_{i=0}^n p_i y^i \\ &= \sum_{i=0}^n p_i \sum_{y=0}^x y^i \end{align}

Now, all we need is a formula for the prefix sum of $y^i$. This is given by Faulhaber's Formula:

$\sum_{y=0}^x y^i = \frac{1}{i+1} \sum_{j=0}^i \binom{i+1}{j} B_j x^{i+1-j}$

where $B_j$ is the $j$th Bernoulli number. The formula only applies for positive values of $i$, so we have to handle $[x^0]P(x)$ separately. Moreover, we can tell from this formula that the degree of $Q(x)$ will be $n+1$.

Just using the formula above is enough to find $Q(x)$ in $O(n^2)$, but let us go further. From what we know so far, the coefficients of $Q(x)$ would be:

\begin{align} [x^i]Q(x) &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \binom{j+1}{j+1-i} \\ &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \frac{(j+1)!}{i! \cdot (j+1-i)!} \\ &= \frac{1}{i!} \sum_{j=i-1}^n (p_j j!) \cdot \frac{B_{j+1-i}}{(j+1-i)!} \\ \end{align}

This looks suspiciously like a convolution. Let us define $A(x)$ and $B(x)$ as:

$A(x) = \sum_{i=0}^n \frac{B_{n-i}}{(n-i)!} x^i$
$B(x) = \sum_{i=1}^n (p_i \cdot i!)x^i$

Then,

$[x^i] Q(x) = \frac{[x^{i+n-1}](A \cdot B)}{i!}$

We can include the contribution of $[x^0]P(x)$ after this by adding it to $[x^0]Q(x)$ and $[x^1]Q(x)$. This way, we can calculate $Q(x)$ in $O(n \log n)$ using FFT.

Finally, we need to tackle the problem of calculating the Bernoulli numbers. We could use the recursive formula on the Wikipedia page, but that's $O(n^2)$. Instead, we can use the exponential generating function of the Bernoulli numbers:

$\frac{x}{e^x-1} = \left(\sum_i \frac{x^i}{(i+1)!} \right)^{-1}$

Now, we can solve the entire problem in $O(n \log{n})$.

I'd like to thank neal since I only found this technique by looking at his submission for ARC 104 E. I later found out that this same idea is used in the problem SERSUM by chemthan, but I decided to make the blog anyway to introduce it to more people.

Edit: I've also put this on my personal blog. I'll probably put less CF blog-worthy things there in the future.

• +111

By Lain, history, 3 years ago,

The round is starting in around half an hour. Let's discuss the approaches here after it's done.

Good luck!

• +147

By Lain, history, 3 years ago,

The above image is a problem from a recent hiring test by CodeNation. Any clues on how to solve it?

P.S. This test is over, it's been a couple days now

• +28

By Lain, history, 3 years ago,

### The Problem

I am trying to solve problem 1136E, where I need to find the lowest $pos$ such that $b_{pos} \geq b_i + x$. I generally use the lazy segment tree from the AtCoder Library, which is iterative. In a recursive segment tree, I could just move down the tree choosing the left or right node. How do I do this in an iterative segment tree?

### My attempt

int find_pos(int val)
{
int root = 1;
while (root < size)
{
push(root);
int l = 2*root;
int r = 2*root+1;
if (t[l].mx >= val)
root = l;
else
root = r;
}
return root-size;
}

Reference submission

This gives the wrong lower bound on some cases. I think it's because in the iterative case, it is not a clear tree, but rather a set of binary trees. Usually we move bottom up when calculating in an iterative segtree, so either it is not possible in an iterative segtree (without magic) or I have misunderstood something. Please let me know.

• +12