N-dimensional function computation

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)$.

-
I think you may need to clarify some terminology here which, at least I, am not familiar with. What do you mean by a function being a partial sum of another function and what do you mean by deriving the value of F' "applied for" a number of intervals? – Tilo Wiklund Aug 7 '11 at 18:49
I have added Latex to your post. Please check and make sure I didn't make any errors. – mixedmath Aug 7 '11 at 19:13
I am sorry to be a bore, but some things are still somewhat unclear. It looks like you are trying to find a closed form for a recurrence relation with two indices, is this correct? Perhaps it would help if you wrote a little about the context where this problem arose? – Tilo Wiklund Aug 7 '11 at 19:15
@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). – Anton Postnikov Aug 7 '11 at 19:22

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)).$$

-
That is fine, thank you! – Anton Postnikov Aug 8 '11 at 11:51

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.

-