2
$\begingroup$

There is a well-known concept of partial sums. I know how to apply it to the 1D, 2D and 3D. Suppose, we have N-dimensional function $F(X_1, X_2,\; \dots \;, X_n)$ which is a partial sum of some function F' in this context. How can we derive the value of F' applied for $A_1\leq X_1 \leq A_2$, $B_1 \leq X_2 \leq B_2$, ... with the knowledge of function $F$ for each co-ordinate?

e.g. for 2D case: F(x, y) = F'(x,y) + F(x - 1, y) + F(x, y - 1) - F(x - 1, y - 1).
We need $T =$ sum of F' values for $x_1 \leq x \leq x_2$, $y_1 \leq y \leq y_2$. So, the result is $T = F(x_2, y_2) - F(x_2, y_1 - 1) - F(x_1 - 1, y_2) + F(x_1 - 1, y_1 - 1)$.

  • 0
    @Tilo: I have function of n parameters (points), this function represents sum of values F' in all cells where each coordinate is not greater than corresponding, so I have function of values in some hypercube with corners (0, 0, ..., 0) and (x1, x2, ..., xn). I want to recover sum of F' in the hupercube with corners (x1, x2, ..., xn) and (y1, y2, ..., yn).2011-08-07

2 Answers 2

3

If I understand you right, you have a some function $f: \mathbb Z^n \to \mathbb R$ and its partial sum

$F(y_1, y_2, \ldots, y_n) = \sum_{x_1=-\infty}^{y_1}\;\sum_{x_2=-\infty}^{y_2} \cdots \sum_{x_n=-\infty}^{y_n} f(x_1, x_2, \ldots, x_n). $

You want to calculate

$T = \sum_{x_1=a_1}^{b_1}\;\sum_{x_2=a_2}^{b_2} \cdots \sum_{x_n=a_n}^{b_n} f(x_1, x_2, \ldots, x_n) $

for some given limits $a_k \le b_k$, $1 \le k \le n$, using only the values of $F$.

If so, this seems like a straightforward application of the inclusion-exclusion principle. Specifically,

$\begin{aligned} T &= F(b_1, b_2, \ldots, b_n) \\ &-\ F(a_1-1, b_2, \ldots, b_n) - F(b_1, a_2-1, \ldots, b_n) - \cdots \\ &+\ F(a_1-1, a_2-1, \ldots, b_n) + \cdots \\ &\;\vdots \\ &\pm\ F(a_1-1, a_2-1, \ldots, a_n-1) \end{aligned}$

where the terms range over all the possible combinations of $a_k-1$ and $b_k$, and the sign of each term is positive if the number of $a_k-1$ parameters is even and negative if it is odd.

More formally, let

$q_k(\xi) = \begin{cases} a_k-1 & \text{if the }k\text{-th lowest binary digit of }\xi\text{ is 1} \\ b_k & \text{if the }k\text{-th lowest binary digit of }\xi\text{ is 0} \end{cases}$

and let

$\sigma(\xi) = \begin{cases} \phantom +1 & \text{if the sum of the binary digits of }\xi\text{ is even} \\ -1 & \text{if the sum of the binary digits of }\xi\text{ is odd.} \end{cases}$

Then

$T = \sum_{\xi=0}^{2^n-1} \sigma(\xi)\ F(q_1(\xi), q_2(\xi), \ldots, q_n(\xi)). $

  • 0
    That is fine, thank you!2011-08-08
2

Here’s a partial answer to get you started. If I understand this correctly, you have in general F(a_1,\dots,a_n) = \sum\limits_{x_1=0}^{a_1}\sum\limits_{x_2=0}^{a_2}\dots\sum\limits_{x_n=0}^{a_n}F'(x_1,\dots,x_n). For each $S \subseteq \{1,\dots,n\}$ let $F^S(a_1,\dots,a_n) = F(b_1,\dots,b_n)$, where $b_k = a_k-1$ if $k \in S$, and $b_k = a_k$ otherwise.

Now suppose that $0 \le c_k \le a_k$ for $k=1,\dots,n$, and let $S = \left\{k \in \{1,\dots,n\}: c_k < a_k \right\}$. The term F'(c_1,\dots,c_n) is included in the sum $F^T(a_1,\dots,a_n)$ iff $T \subseteq S$. Let $G(a_1,\dots,a_n) = \sum\limits_{k=1}^n (-1)^{k+1}\sum\limits_{|T|=k}F^T(a_1,\dots,a_n),$ where it’s understood that $T$ in the inner sum ranges over subsets of $\{1,\dots,n\}$. The term F'(c_1,\dots,c_n) is counted $\sum\limits_{k=1}^{|S|}(-1)^{k+1}\binom{|S|}{k}$ times in this sum. But $\sum\limits_{k=1}^{|S|}(-1)^{k+1}\binom{|S|}{k} = (-1)\sum\limits_{k=1}^{|S|}(-1)^k \binom{|S|}{k} = (-1)\left(\sum\limits_{k=0}^{|S|}(-1)^k \binom{|S|}{k} - 1\right) = 1$, so F(a_1,\dots,a_n) = F'(a_1,\dots,a_n)+G(a_1,\dots,a_n), and \begin{align*} F'(a_1,\dots,a_n) &= F(a_1,\dots,a_n) - \sum\limits_{k=1}^n (-1)^{k+1}\sum\limits_{|T|=k}F^T(a_1,\dots,a_n) \\ &= F(a_1,\dots,a_n) + \sum\limits_{k=1}^n (-1)^k\sum\limits_{|T|=k}F^T(a_1,\dots,a_n). \end{align*} When $n=2$ this essentially reduces to your formula F(x,y) = F'(x,y) + F(x-1,y) + F(x,y-1) - F(x-1,y-1).

There are adjustments to be made when one or more of the $a_k$ are $0$, but apart from that, this recovers F' from $F$, and from that it shouldn’t be too hard to get the interval sums that you want. If I have time later (and no one beats me to it) I’ll work those out as well.