## Abstract

This paper is dedicated to the counting problem of writing an integer number $z$ as a sum of an ordered sequence of $n$ integers from $n$ given intervals, i.e., counting the number of configurations $(z_1,…,z_n)$ with $z=z_1+...+z_n$ for zi\in[x_i,y_i] with integers x_i and y_i and 1\leq i\leq n. We show an algorithm computing this number in $\bigo(n_z lg n)$ average time, and a data structure computing this number in $\bigo(n)$ time, independently of $z$. The data structure is constructed in \bigo(2^nn^3)$time. Its construction algorithm only depends on the intervals$[x_i,y_i] (1\leq i\leq n)$. This construction algorithm can be parallelized with$p=\bigo(n^3)$processors, yielding$\bigo(2^n\frac{n^3}{p})\$ construction time with high probability.