Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.