pith. machine review for the scientific record. sign in

arxiv: 2605.06555 · v1 · submitted 2026-05-07 · 💻 cs.DS

Recognition: unknown

Fast decremental tree sums in forests

Benjamin Aram Berendsohn, Marek Soko{\l}owski

Pith reviewed 2026-05-08 05:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords decremental algorithmsdynamic foreststree sumsmicro-macro decompositiondata structuresoptimal algorithmsgroup modeledge deletions
0
0 comments X

The pith

Micro-macro tree decompositions maintain sums over vertex weights in forests under only deletions in O(log* n) time per operation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how to keep track of the total weight of each connected component in a forest as edges are deleted and weights are updated. Standard fully dynamic structures solve this in O(log n) time, but the authors focus on the deletion-only setting to see if faster methods exist. They develop a data structure that preprocesses the initial forest in linear time and then answers queries or handles updates in O(log* n) time using a decomposition into micro and macro trees. When all weights are fixed at one, the per-operation time falls to constant. They also give a second algorithm that matches the exact number of arithmetic operations needed by an optimal solution for any fixed starting forest.

Core claim

We give a data structure with O(n) preprocessing time and O(log* n) time per operation, based on a micro-macro tree decomposition. If the forest is unweighted, the operation time can be improved to O(1). Additionally, we give an asymptotically universally optimal algorithm that processes m operations on an initial forest F in running time O(OPT(F, m)), where OPT(F, m) is the number of weight additions and subtractions performed by a best possible algorithm on a worst-case instance.

What carries the argument

A micro-macro tree decomposition that breaks the forest into small precomputable pieces and larger navigable structures to support fast sum maintenance after deletions.

If this is right

  • Component sums can be maintained faster when the input is known to be deletion-only rather than fully dynamic.
  • Unweighted forests allow constant-time sum queries after linear preprocessing.
  • The optimal algorithm achieves running time proportional to the minimum number of arithmetic steps any solution must perform for the given starting forest.
  • Tight time bounds are established for several variants of the related subtree-sum problem on rooted forests.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The logarithmic factor in standard dynamic-tree methods appears tied to the need to support insertions, not deletions alone.
  • Similar decomposition techniques may accelerate other deletion-only problems such as connectivity or path aggregates on trees.
  • Precomputing optimal small-instance solutions could be applied to other decremental problems where OPT can be bounded in advance.
  • The unknown worst-case complexity of the optimal algorithm leaves open whether O(log* n) is improvable to O(1) in the general weighted case.

Load-bearing premise

The initial forest is supplied all at once and the only changes afterward are edge deletions and weight updates, with no new edges ever added.

What would settle it

A concrete sequence of deletions and weight updates on a forest of size n where the maintained sums require more than O(log* n) operations on average in the group model would contradict the claimed bounds.

read the original abstract

We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size $n$ under edge deletions, weight updates, and a certain information-retrieval query. Both problems can be solved in $O(\log n)$ time per update/query using standard dynamic forest data structures like top trees, even if additionally edge insertions are allowed. We investigate whether the deletion-only problem can be solved faster. First, we consider $\texttt{tree-sum}$ queries, where we ask for the sum of vertex weights in one of the connected components (i.e., trees) in the forest. We give a data structure with $O(n)$ preprocessing time and $O(\log^* n)$ time per operation, based on a micro-macro tree decomposition (Alstrup et al., 1997). If the forest is unweighted (i.e., all weights are 1 and cannot be changed), then the operation time can be improved to $O(1)$. Additionally, we give an asymptotically universally optimal algorithm. More specifically, our algorithm works in the group model, and processes $m$ operations on an initial forest $F$ in running time $O( \mathrm{OPT}(F, m) )$. Here $\mathrm{OPT}(F, m)$ is the number of weight additions and subtractions that a best possible algorithm performs to handle a worst-case instance for a fixed initial forest $F$ and a fixed number $m$ of operations. We achieve this with a combination of the aforementioned decomposition technique, precomputation of optimal data structures for very small instances, and some insights into the behavior of $\mathrm{OPT}$. Note that even the worst-case complexity of this algorithm remains unknown to us. Second, we consider $\texttt{subtree-sum}$ queries. Here, the forest is rooted, and a query $\texttt{subtree-sum}(v)$ returns the sum of weights in the subtree rooted at $v$. We show tight bounds for several variants of this problem. [...]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript studies two decremental dynamic problems on vertex-weighted forests of size n under edge deletions and weight updates. For tree-sum queries (sum of weights in a connected component), it claims an O(n)-preprocessing data structure achieving O(log* n) time per operation via micro-macro tree decomposition (Alstrup et al. 1997), improving to O(1) when the forest is unweighted. It further presents an asymptotically universally optimal algorithm in the group model that processes m operations in O(OPT(F, m)) time, where OPT is the minimum number of weight additions/subtractions needed by any algorithm on a fixed initial forest F. For subtree-sum queries on rooted forests, tight bounds are shown for several variants.

Significance. If the bounds and optimality hold, the work improves on the O(log n) per-operation time of standard structures such as top trees in the strictly decremental setting. The micro-macro decomposition with upfront precomputation, the O(1) unweighted case, and the group-model universal optimality (even while leaving worst-case complexity open) are notable strengths that could inform other deletion-only dynamic graph problems.

major comments (2)
  1. [Micro-macro decomposition and update handling] The description of how the micro-macro decomposition is maintained under deletions (rather than rebuilt) should include an explicit accounting of the auxiliary information stored during the O(n) preprocessing and how deletions affect the macro-tree structure without introducing hidden logarithmic factors.
  2. [Universally optimal algorithm] The group-model optimality argument combines the decomposition with precomputation on small instances and insights into OPT behavior; a concrete reduction or invariant should be stated showing that the total number of additions/subtractions across all operations is at most OPT(F, m) plus lower-order terms.
minor comments (3)
  1. [Abstract] The abstract is truncated after the subtree-sum sentence; the final version should concisely state the tight bounds obtained for the subtree-sum variants.
  2. [Preliminaries] Notation for the group model and the definition of OPT(F, m) should be introduced with a short self-contained paragraph before the optimality theorem.
  3. [Introduction] A table comparing the new bounds against top trees and other dynamic-forest structures would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and the recommendation for minor revision. The comments are helpful for improving the clarity of our presentation. We address each major comment below and will incorporate the suggested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: The description of how the micro-macro decomposition is maintained under deletions (rather than rebuilt) should include an explicit accounting of the auxiliary information stored during the O(n) preprocessing and how deletions affect the macro-tree structure without introducing hidden logarithmic factors.

    Authors: We agree that an explicit accounting would enhance the exposition. In the revised version, we will add a new subsection detailing the auxiliary information: during O(n) preprocessing, we store for each micro-tree its internal sum, boundary pointers to the macro-tree, and precomputed deletion tables for all possible deletion sequences within the micro-tree. Deletions are handled by updating the affected micro-tree in constant time using these tables, and only when a deletion disconnects a macro-node do we update the macro-tree structure. Since the micro-macro decomposition ensures that the macro-tree has height O(log* n), and each update affects O(1) macro-nodes per level, the per-operation time remains O(log* n) without hidden factors. We will include a formal proof that the total auxiliary space is linear and no additional logarithmic overhead is incurred. revision: yes

  2. Referee: The group-model optimality argument combines the decomposition with precomputation on small instances and insights into OPT behavior; a concrete reduction or invariant should be stated showing that the total number of additions/subtractions across all operations is at most OPT(F, m) plus lower-order terms.

    Authors: We appreciate this observation. To make the argument more rigorous, we will introduce in the revised manuscript an explicit invariant: at any point, the data structure maintains a representation where the number of additions/subtractions performed so far is at most OPT(F, t) + O(t), where t is the number of operations so far. This is achieved by precomputing optimal solutions for all small forests of size up to some constant (using the group model allowing free precomputation), and using the decomposition to reduce large instances to small ones. We will state a reduction showing that our algorithm's cost is bounded by OPT plus lower-order terms, specifically O(m) additional operations which are absorbed since OPT(F,m) = Omega(m) in the worst case for nontrivial instances. This preserves the asymptotic universal optimality. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives its O(log* n) and O(1) bounds from an external micro-macro decomposition (Alstrup et al. 1997) precomputed on the initial forest, plus new precomputation for small instances and group-model analysis of OPT(F, m). No step reduces a claimed prediction or bound to a fitted parameter, self-definition, or load-bearing self-citation; the universally optimal claim is supported by explicit combination of decomposition, precomputation, and OPT insights without circular reduction to inputs. The derivation remains self-contained against the stated decremental setting.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Claims rest on the micro-macro tree decomposition from prior literature, standard RAM-model assumptions for time bounds, and precomputation for small instances; no free parameters or new entities are introduced.

axioms (1)
  • standard math Standard model of computation (RAM) for analyzing dynamic data structure operations.
    Used to establish the O(log* n) and O(1) time bounds.

pith-pipeline@v0.9.0 · 5680 in / 1197 out tokens · 66165 ms · 2026-05-08T05:40:07.370279+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 35 canonical work pages

  1. [1]

    Peyman Afshani, J \' e r \' e my Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. J. ACM , 64(1):3:1--3:38, 2017. https://doi.org/10.1145/3046673 doi:10.1145/3046673

    work page doi:10.1145/3046673 2017

  2. [2]

    V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Farad z ev. On economical construction of the transitive closure of a directed graph. Doklady Akademii Nauk SSSR , 194(3):1209--1210, 1970. Russian

    1970

  3. [3]

    Maintaining information in fully dynamic trees with top trees

    Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms , 1(2):243--264, 2005. https://doi.org/10.1145/1103963.1103966 doi:10.1145/1103963.1103966

    work page doi:10.1145/1103963.1103966 2005

  4. [4]

    4 Ingo Althöfer, Gautam Das, David P

    Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked ancestor problems. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998 , pages 534--544. IEEE Computer Society, 1998. https://doi.org/10.1109/SFCS.1998.743504 doi:10.1109/SFCS.1998.743504

    work page doi:10.1109/sfcs.1998.743504 1998

  5. [5]

    Secher, and Maz Spork

    Stephen Alstrup, Jens P. Secher, and Maz Spork. Optimal on-line decremental connectivity in trees. Inf. Process. Lett. , 64(4):161--164, 1997. https://doi.org/10.1016/S0020-0190(97)00170-1 doi:10.1016/S0020-0190(97)00170-1

    work page doi:10.1016/s0020-0190(97)00170-1 1997

  6. [6]

    Universally optimal decremental tree minima, 2026

    Benjamin Aram Berendsohn. Universally optimal decremental tree minima, 2026. https://arxiv.org/abs/2602.15977 arXiv:2602.15977

    work page arXiv 2026

  7. [7]

    LATIN 2000: Theoretical Informatics

    Michael A. Bender and Martin Farach - Colton. The LCA problem revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings , volume 1776 of Lecture Notes in Computer Science , pages 88--94. Springer, 2000. https://doi.o...

    work page doi:10.1007/10719839 2000

  8. [8]

    Bender and Martin Farach - Colton

    Michael A. Bender and Martin Farach - Colton. The level ancestor problem simplified. Theor. Comput. Sci. , 321(1):5--12, 2004. https://doi.org/10.1016/J.TCS.2003.05.002 doi:10.1016/J.TCS.2003.05.002

    work page doi:10.1016/j.tcs.2003.05.002 2004

  9. [9]

    Jon Louis Bentley and Hermann A. Maurer. Efficient worst-case data structures for range searching. Acta Informatica , 13:155--168, 1980. https://doi.org/10.1007/BF00263991 doi:10.1007/BF00263991

    work page doi:10.1007/bf00263991 1980

  10. [10]

    Finding level-ancestors in trees

    Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci. , 48(2):214--230, 1994. https://doi.org/10.1016/S0022-0000(05)80002-9 doi:10.1016/S0022-0000(05)80002-9

    work page doi:10.1016/s0022-0000(05)80002-9 1994

  11. [11]

    o rg - R \

    Paul F. Dietz. Optimal algorithms for list indexing and subset rank. In Frank K. H. A. Dehne, J \" o rg - R \" u diger Sack, and Nicola Santoro, editors, Algorithms and Data Structures, Workshop WADS '89, Ottawa, Canada, August 17-19, 1989, Proceedings , volume 382 of Lecture Notes in Computer Science , pages 39--46. Springer, 1989. https://doi.org/10.100...

    work page doi:10.1007/3-540-51542-9 1989

  12. [12]

    An on-line edge-deletion problem

    Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. J. ACM , 28(1):1--4, 1981. https://doi.org/10.1145/322234.322235 doi:10.1145/322234.322235

    work page doi:10.1145/322234.322235 1981

  13. [13]

    Peter M. Fenwick. A new data structure for cumulative frequency tables. Softw. Pract. Exp. , 24(3):327--336, 1994. https://doi.org/10.1002/SPE.4380240306 doi:10.1002/SPE.4380240306

    work page doi:10.1002/spe.4380240306 1994

  14. [14]

    Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. J. ACM , 29(1):250--260, 1982. https://doi.org/10.1145/322290.322305 doi:10.1145/322290.322305

    work page doi:10.1145/322290.322305 1982

  15. [15]

    Fredman and M

    M. Fredman and M. Saks. The Cell Probe Complexity of Dynamic Data Structures . In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , STOC ’89, pages 345--354, New York, NY, USA, 1989. Association for Computing Machinery. https://doi.org/10.1145/73007.73040 doi:10.1145/73007.73040

    work page doi:10.1145/73007.73040 1989

  16. [16]

    Fredman and Dan E

    Michael L. Fredman and Dan E. Willard. BLASTING through the information theoretic barrier with FUSION TREES . In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA , pages 1--7. ACM , 1990. https://doi.org/10.1145/100216.100217 doi:10.1145/100216.100217

    work page doi:10.1145/100216.100217 1990

  17. [17]

    Galler and Michael J

    Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. Commun. ACM , 7(5):301--303, 1964. https://doi.org/10.1145/364099.364331 doi:10.1145/364099.364331

    work page doi:10.1145/364099.364331 1964

  18. [18]

    Gabow and Robert Endre Tarjan

    Harold N. Gabow and Robert Endre Tarjan. A linear-time algorithm for a special case of D isjoint S et U nion. J. Comput. Syst. Sci. , 30(2):209--221, 1985. https://doi.org/10.1016/0022-0000(85)90014-5 doi:10.1016/0022-0000(85)90014-5

    work page doi:10.1016/0022-0000(85)90014-5 1985

  19. [19]

    Tarjan, and Jakub Tetek

    Bernhard Haeupler, Richard Hlad \' k, John Iacono, V \' a clav Rozhon, Robert E. Tarjan, and Jakub Tetek. Fast and simple sorting using partial information. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 3953--3973. SIAM ,...

    work page doi:10.1137/1.9781611978322.134 2025

  20. [20]

    Fully dynamic connectivity in O( n( n)^2) amortized expected time

    Shang - En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Fully dynamic connectivity in O( n( n)^2) amortized expected time. TheoretiCS , 2, 2023. https://doi.org/10.46298/THEORETICS.23.6 doi:10.46298/THEORETICS.23.6

    work page doi:10.46298/theoretics.23.6 2023

  21. [21]

    Improved Distance (Sensitivity) Oracles with Subquadratic Space

    Bernhard Haeupler, Richard Hlad \' k, V \' a clav Rozhon, Robert E. Tarjan, and Jakub Tetek. Universal optimality of D ijkstra via beyond-worst-case heaps. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 2099--2130. IEEE , 2024. https://doi.org/10.1109/FOCS61266.2024.00125 doi:10.1...

    work page doi:10.1109/focs61266.2024.00125 2024

  22. [22]

    Hopcroft and Jeffrey D

    John E. Hopcroft and Jeffrey D. Ullman. Set merging algorithms. SIAM J. Comput. , 2(4):294--303, 1973. https://doi.org/10.1137/0202024 doi:10.1137/0202024

    work page doi:10.1137/0202024 1973

  23. [23]

    Universally-optimal distributed algorithms for known topologies

    Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1166--1179. ACM , 2021. https://doi.org/10.1145/3406325.3451081 doi:1...

    work page doi:10.1145/3406325.3451081 2021

  24. [24]

    Neil D. Jones. Computability and complexity - from a programming perspective . Foundations of computing series. MIT Press, 1997

    1997

  25. [25]

    Lawrence L. Larmore. An optimal algorithm with unknown time complexity for convex matrix searching. Inf. Process. Lett. , 36(3):147--151, 1990. https://doi.org/10.1016/0020-0190(90)90084-B doi:10.1016/0020-0190(90)90084-B

    work page doi:10.1016/0020-0190(90)90084-b 1990

  26. [26]

    Optimal decremental connectivity in planar graphs

    Jakub a cki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. Theory Comput. Syst. , 61(4):1037--1053, 2017. https://doi.org/10.1007/S00224-016-9709-X doi:10.1007/S00224-016-9709-X

    work page doi:10.1007/s00224-016-9709-x 2017

  27. [27]

    Range searching with efficient hierarchical cuttings

    Jir \' Matousek. Range searching with efficient hierarchical cuttings. In David Avis, editor, Proceedings of the Eighth Annual Symposium on Computational Geometry, Berlin, Germany, June 10-12, 1992 , pages 276--285. ACM , 1992. https://doi.org/10.1145/142675.142732 doi:10.1145/142675.142732

    work page doi:10.1145/142675.142732 1992

  28. [28]

    Lower bound techniques for data structures

    Mihai P a tra s cu. Lower bound techniques for data structures . PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA , 2008. URL: https://hdl.handle.net/1721.1/45866

    2008

  29. [29]

    Mihai P a tra s cu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. , 35(4):932--963, 2006. https://doi.org/10.1137/S0097539705447256 doi:10.1137/S0097539705447256

    work page doi:10.1137/s0097539705447256 2006

  30. [30]

    An Optimal Minimum Spanning Tree Algorithm

    Seth Pettie and Vijaya Ramachandran. An Optimal Minimum Spanning Tree Algorithm . J. ACM , 49(1):16--34, January 2002. https://doi.org/10.1145/505241.505243 doi:10.1145/505241.505243

    work page doi:10.1145/505241.505243 2002

  31. [31]

    A shortest path algorithm for real-weighted undirected graphs

    Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. , 34(6):1398--1431, 2005. https://doi.org/10.1137/S0097539702419650 doi:10.1137/S0097539702419650

    work page doi:10.1137/s0097539702419650 2005

  32. [32]

    Sleator and Robert

    Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. , 26(3):362--391, 1983. https://doi.org/10.1016/0022-0000(83)90006-5 doi:10.1016/0022-0000(83)90006-5

    work page doi:10.1016/0022-0000(83)90006-5 1983

  33. [33]

    Efficiency of a good but not linear set union algorithm

    Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM , 22(2):215--225, 1975. https://doi.org/10.1145/321879.321884 doi:10.1145/321879.321884

    work page doi:10.1145/321879.321884 1975

  34. [34]

    A class of algorithms which require nonlinear time to maintain disjoint sets

    Robert Endre Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. , 18(2):110--127, 1979. https://doi.org/10.1016/0022-0000(79)90042-4 doi:10.1016/0022-0000(79)90042-4

    work page doi:10.1016/0022-0000(79)90042-4 1979

  35. [35]

    A combinatorial proof of universal optimality for computing a planar convex hull

    Ivor van der Hoog , Eva Rotenberg, and Daniel Rutschmann. A combinatorial proof of universal optimality for computing a planar convex hull. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025 , volume 351 of LIPIcs , pages 102:1--102:13. Sc...

    work page doi:10.4230/lipics.esa.2025.102 2025

  36. [36]

    29 Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann

    Ivor van der Hoog , Eva Rotenberg, and Daniel Rutschmann. Simpler optimal sorting from a directed acyclic graph. In Ioana Oriana Bercea and Rasmus Pagh, editors, 2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 350--355. SIAM , 2025. https://doi.org/10.1137/1.9781611978315.26 doi:10.1137/1.9781611978315.26

    work page doi:10.1137/1.9781611978315.26 2025

  37. [37]

    33 Jean Vuillemin

    Ivor van der Hoog , Eva Rotenberg, and Daniel Rutschmann. Simpler universally optimal D ijkstra. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025 , volume 351 of LIPIcs , pages 71:1--71:9. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Info...

    work page doi:10.4230/lipics.esa.2025.71 2025

  38. [38]

    On the complexity of maintaining partial sums

    Andrew Chi - Chih Yao. On the complexity of maintaining partial sums. SIAM J. Comput. , 14(2):277--288, 1985. https://doi.org/10.1137/0214022 doi:10.1137/0214022

    work page doi:10.1137/0214022 1985