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