<figure><img src="image_1.png" /></figure>

HAL
open science

# Maintaining partial sums in logarithmic time

Jochen Burghardt

► To cite this version:

Jochen Burghardt. Maintaining partial sums in logarithmic time. Nordic Journal of Computing, 2001, 8 (4). hal-02913376

HAL Id: hal-02913376

https://hal.science/hal-02913376

Submitted on 8 Aug 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Maintaining partial sums in logarithmic time

Jochen Burghardt

Berlin

## Abstract

We present a data structure that allows to maintain in logarithmic time all partial sums of elements of a linear array during incremental changes of element's values.

Key words: Partial sums; Data structures; Algorithms

## 1 Motivation

Assume you have a linear array $x_0, \dots, x_{N-1}$ of numbers which are frequently updated, and you need to maintain all partial sums $\sum_{i=j}^k x_i$, where $0 \le j \le k < N$. We present a data structure that allows to access each $x_k$ and to compute any partial sum in time $O(\log(N))$.

As an application, think of the $x_k$ as integer numbers indicating the probabilities of certain events; by choosing a uniformly distributed random number $r$ in the range $0 \le r < \sum_{i=0}^{N-1} x_i$ and selecting the unique $k \in \{0, \dots, N\}$ with $\sum_{i=k}^{N-1} x_i \le r < \sum_{i=k-1}^{N-1} x_i$, event $k$ is selected with probability $\frac{x_k}{\sum_{i=0}^{N-1} x_i}$.

If the probability distribution of events changes frequently, the partial sums need to be recomputed every time, which takes time $O(N)$ using the naive algorithm.

## 2 Data structure and access algorithms

Our solution is to store a mix of individual values $x_i$ and partial sums in the array, thus realizing a binary tree where each node represents the sum of all leafs below it. Figure 1 sketches an example for $N = 16$, the partial sums corresponding to the nodes indicated by solid circles are stored as $s_i$.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Data structure</figcaption></figure>

In some respect, this idea is similar to that of heap sort [AHU74, Sect. 3.4], which also uses a mix of representations (sorted along a path and unsorted within a level) to combine the advantages of both. Our data structure combines the advantages of storing single values (easily updatable) and sums (no need to recompute them).

Formally, let $N$ be a power of 2; let an array $x_0, \dots, x_{N-1}$ of size $N$ be given. Instead of this original array, we maintain the array $s_0, \dots, s_{N-1}$, where

$$s_k := \sum_{i=0}^{\text{gcd}(N,k)-1} x_{k+i} \qquad (1)$$

Here, $\text{gcd}(N, k)$ is the greatest common divisor of $N$ and $k$, i.e., the largest power of 2 dividing $k$. It corresponds to the least 1 bit in the 2-complement representation of $k$, which can be computed as bitwise and of $N+k$ and $N-k$.

The following algorithms, given in C code in Fig. 2, maintain our data structure.

* `int sumN(int k)` returns $\sum_{i=k}^{N-1} x_i$;

* `int sum(int j,k)` returns $\sum_{i=j}^{k} x_i$;

* `int get(int k)` retrieves $x_k$;

* `void inc(int k,x)` adds $x$ to $x_k$;

* `void set(int k,x)` assigns $x$ to $x_k$; and

* `int find(int x)` returns some $k$ such that $\sum_{i=k+1}^{N-1} x_i \le x < \sum_{i=k}^{N-1} x_i$, provided $0 \le x < \sum_{i=0}^{N-1} x_i$; $k$ is unique if no $x_i$ is negative.

Figure 3 shows some sample runs on the data in Fig. 1.

In order to deal with arrays whose size is not a power of 2, assume $s_k = 0$ for all $k \ge M$, where $N/2 < M \le N$. At two places it is necessary to test the index boundary explicitly, using the function `int S(int i)`.

The algorithms can immediately be generalized to deal with arbitrary (non-
```c
int s[M];

#define S(i)          (i<M ? s[i] : 0)
#define gcdN(k)       ((N+k) & (N-k))

int sumN(int k) {
    int i, sm = 0;
    for (i=k; i<M; i+=gcdN(i))
        sm += s[i];
    return sm;
}

#define sum(j,k)     (sumN(j) - sumN(k+1))

int get(int k) {
    int i, x = s[k];
    for (i=1; i<gcdN(k) && k+i<M; i*=2)
        x -= s[k+i];
    return x;
}

void inc(int k,x) {
    int i;
    for (i=k; i>=0; i-=gcdN(i))
        s[i] += x;
}

#define set(k,x)     inc(k,x-get(k))

int find(int x) {
    int i, k = 0, pv = s[N/2];
    for (i=N/2; i>0; i/=2)
        if (x < pv) {
            pv += S(k+i*3/2) - s[k+i];
            k += i;
        } else {
            pv += S(k+i/2);
        }
    return k;
}
```

<caption>Fig. 2. Algorithms</caption>
<figure><img src="image_3.png" /><figcaption>Fig. 3. Sample runs</figcaption></figure>

abelian) group elements instead of integers; if `find` is to be used, ordered groups are necessary.

## 3 Complexity

All algorithms take $O(\log N)$ time due to the implicit tree structure. For `sumN` and `inc`, note that the value of `gcd(N, i)` grows in every loop cycle, since

$$ \gcd(N, i \pm \gcd(N, i)) \ge 2 \cdot \gcd(N, i). \quad (2) $$

In the following sections 4 to 7, we give correctness proofs of the main algorithms in the Hoare calculus [Hoa69].

## 4 Correctness of get

To see the correctness of `get`, show

$$ \sum_{i=1}^{2^a-1} f(i) = \sum_{i=0}^{a-1} \sum_{j=0}^{2^i-1} f(2^i + j) \quad (3) $$

by induction on $a$; note that commutativity of $+$ is not required for the proof.

If $\gcd(N, k) = 2^a$, we have $\gcd(N, k + 2^i) = 2^i$ for $0 \le i < a$, and therefore

$$ s_k \stackrel{(1)}{=} x_k + \sum_{i=1}^{2^a-1} x_{k+i} \stackrel{(3)}{=} x_k + \sum_{i=0}^{a-1} \sum_{j=0}^{2^i-1} x_{k+2^i+j} \stackrel{(1)}{=} x_k + \sum_{i=0}^{a-1} s_{k+2^i}. \quad (4) $$
We define the abbreviation $\Sigma_{k,b} := s_{k+b} + s_{k+2,b} + s_{k+4,b} + \dots + s_{k+\gcd(N,k)/2}$.

By equation (4), we obtain $s_k = x_k + \Sigma_{k,1}$, justifying the step in lines 4.–5.

We have $\Sigma_{k,b} = 0$ if $b \ge \gcd(N, k)$ or $k + b \ge M$; this justifies lines 13.–14.

We can now apply the Hoare calculus to the code of `int get(int k)`:

1. `int get(int k) {`

2. `int i, x;`

3. `x = s[k];`

4. `i = 1;`

5. `x = x_k + \Sigma_{k,i} \wedge i \le \gcd(N, k)`

6. `while (i < gcdN(k) && k+i < M) {`

7. `x = x_k + \Sigma_{k,i} \wedge i < \gcd(N, k)`

8. `x = x - s[k+i];`

9. `x = x_k + \Sigma_{k,2,i} \wedge i < \gcd(N, k)`

10. `i = i * 2;`

11. `x = x_k + \Sigma_{k,i} \wedge i \le \gcd(N, k)`

12. `}`

13. `x = x_k + \Sigma_{k,i} \wedge (i = \gcd(N, k) \lor k + i \ge M)`

14. `return x;`

15. `}`

## 5 Correctness of inc

Next, we show that `inc` makes sufficiently many updates. By (1), $s_i$ depends on $x_k$, iff $i \le k < i + \gcd(N, i)$.

Hence, if $s_i$ depends on $x_k$, then so does $s_{i-\gcd(N,i)}$, since

$$i - \gcd(N, i) \le i \le k \text{ and, by (2),} \\ (i - \gcd(N, i)) + \gcd(N, i - \gcd(N, i)) \ge i + \gcd(N, i) > k.$$

But no $s_{i'}$ for $i - \gcd(N, i) < i' < i$ depends on $x_k$:

Let $i = 2^a \cdot b$ and $i' = 2^{a'} \cdot b'$ for odd numbers $b, b'$.

Then $a' < a$ since $i - \gcd(N, i) = 2^a \cdot (b - 1)$.

And $2^{a'} \cdot b' = i' < i = 2^{a-a'} \cdot 2^{a'} \cdot b$ implies $b' + 1 \le 2^{a-a'} \cdot b$.

Hence, $i' + \gcd(N, i') = 2^{a'} \cdot (b' + 1) \le 2^{a'} \cdot 2^{a-a'} \cdot b = i \le k$.
## 6 Correctness of sumN

The loop in sumN satisfies the invariant $sm = \sum_{j=k}^{i-1} x_j$, since

$$sm + s_i \stackrel{(1)}{=} \left(\sum_{j=k}^{i-1} x_j\right) + \left(\sum_{j=0}^{\gcd(N,i)-1} x_{i+j}\right) = \sum_{j=k}^{i+\gcd(N,i)-1} x_j.$$

This justifies the step in lines 7.–9. For lines 13.–14. note that $x_j = 0$ for $j \ge M$.

1. `int sumN(int k) {`

2. `int i, sm;`

3. `sm = 0;`

4. `i = k;`

5. `sm = \sum_{j=k}^{i-1} x_j`

6. `while (i < M) {`

7. `sm = \sum_{j=k}^{i-1} x_j`

8. `sm = sm + s[i];`

9. `sm = \sum_{j=k}^{i+\gcd(N,i)-1} x_j`

10. `i = i + gcdN(i);`

11. `sm = \sum_{j=k}^{i-1} x_j`

12. `}`

13. `sm = \sum_{j=k}^{i-1} x_j \land i \ge M`

14. `return sm;`

15. `}`

## 7 Correctness of find

The loop in find satisfies the invariant

$$ \begin{array}{l} \sum_{j=k+2 \cdot i}^{N-1} x_j \le x < \sum_{j=k}^{N-1} x_j \quad \text{and} \quad (i \ge 2 \Rightarrow \text{pv} = \sum_{j=k+i}^{N-1} x_j) \\ \phantom{\sum_{j=k+2 \cdot i}^{N-1} x_j \le x < \sum_{j=k}^{N-1} x_j \quad \text{and}} \text{and} \quad \gcd(N, k) \ge \gcd(N, i) = i. \end{array} \qquad (5) $$

To show this, note that for $i \ge 2$, we have

$$ s_{k+i} \stackrel{(1)}{=} \sum_{j=0}^{\gcd(N,k+i)-1} x_{k+i+j} \stackrel{(5)}{=} \sum_{j=0}^{i-1} x_{k+i+j} = \sum_{j=k+i}^{k+2 \cdot i-1} x_j, $$
and similarly

$$s_{k+i/2} = \sum_{j=k+i/2}^{k+i-1} x_j \quad \text{and} \quad s_{k+i \cdot 3/2} = \sum_{j=k+i \cdot 3/2}^{k+2 \cdot i-1} x_j,$$

hence, we get

$$\mathbf{pv} + s_{k+i \cdot 3/2} - s_{k+i} = \sum_{j=k+i \cdot 3/2}^{N-1} x_j \quad \text{and} \quad \mathbf{pv} + s_{k+i/2} = \sum_{j=k+i/2}^{N-1} x_j, \quad (6)$$

in case of $x < pv$ and $x \ge pv$, respectively.

We transform the program to make the Hoare verification rules applicable and unfold the last loop cycle ($i = 1$) to avoid confusing case distinctions. We omit the computation of the pivot element pv in the last cycle, since its value isn't used any more.

We define the abbreviations $\Sigma_a := \sum_{j=a}^{N-1} x_j$ and $p(a, b) := \gcd(N, a) \ge \gcd(N, b) = b$

Observe that $i \ge 2 \land p(k, i)$ implies both $p(k + i, i)$ and $p(k, i/2)$; this is used in lines 13.–15. and 21.–23., respectively.

Equations (6) justify the steps in lines 13.–15. and 19.–21.; equation (1) justifies step 7.–9.

1. $0 \le x < \Sigma_0$

2. `int find(int x) {`

3. `int i, k, pv;`

4. `$\Sigma_N \le x < \Sigma_0$`

5. `k = 0;`

6. `i = N/2;`

7. `$\Sigma_{k+2 \cdot i} \le x < \Sigma_k \land p(k, i) \land i \ge 1$`

8. `pv = s[N/2];`

9. `$\Sigma_{k+2 \cdot i} \le x < \Sigma_k \land pv = \Sigma_{k+i} \land p(k, i) \land i \ge 1$`

10. `while (i >= 2) {`

11. `$\Sigma_{k+2 \cdot i} \le x < \Sigma_k \land pv = \Sigma_{k+i} \land p(k, i) \land i \ge 2$`

12. `if (x < pv) {`

13. `$\Sigma_{k+2 \cdot i} \le x < \Sigma_{k+i} \land pv = \Sigma_{k+i} \land p(k, i) \land i \ge 2$`

14. `pv = pv + S(k+i*3/2) - s[k+i];`

15. `$\Sigma_{k+2 \cdot i} \le x < \Sigma_{k+i} \land pv = \Sigma_{k+3 \cdot i/2} \land p(k+i, i) \land i \ge 2$`

16. `k = k + i;`

17. `$\Sigma_{k+i} \le x < \Sigma_k \land pv = \Sigma_{k+i/2} \land p(k, i) \land i \ge 2$`

18. `} else {`
19. $\Sigma_{k+i} \le x < \Sigma_k \land pv = \Sigma_{k+i} \land p(k, i) \land i \ge 2$
20. $pv = pv + S(k+i/2)$;
21. $\Sigma_{k+i} \le x < \Sigma_k \land pv = \Sigma_{k+i/2} \land p(k, i) \land i \ge 2$
22. }
23. $\Sigma_{k+i} \le x < \Sigma_k \land pv = \Sigma_{k+i/2} \land p(k, i/2) \land i \ge 2$
24. $i = i/2$;
25. $\Sigma_{k+2·i} \le x < \Sigma_k \land pv = \Sigma_{k+i} \land p(k, i) \land i \ge 1$
26. }
27. $\Sigma_{k+2} \le x < \Sigma_k \land pv = \Sigma_{k+1} \land i = 1$
28. if ($x < pv$) {
29. $\Sigma_{k+2} \le x < \Sigma_{k+1} \land pv = \Sigma_{k+1}$
30. $k = k + 1$;
31. $\Sigma_{k+1} \le x < \Sigma_k$
32. } else {
33. $\Sigma_{k+1} \le x < \Sigma_k$
34. }
35. $\Sigma_{k+1} \le x < \Sigma_k$
36. return $k$;
37. }

This completes the verification proofs of the algorithms given in Fig. 2.
A short version of this paper (without proofs) was published in [Bur01].

References

[AHU74] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. *The Design and Analysis of Computer Algorithms*. Addison-Wesley, 1974.

[Bur01] Jochen Burghardt. Maintaining partial sums in logarithmic time. *Nordic Journal of Computing*, 8(4):473–474, 2001.

[Hoa69] C.A.R. Hoare. An axiomatic basis for computer programming. *C.ACM*, 12(10):576–583, Oct 1969.