Pith. sign in

REVIEW 1 cited by

A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2403.03990 v1 pith:MDZ7FCWE submitted 2024-03-06 cs.DS

Brent Harrison , Jason Necaise , Andrew Projansky , James D. Whitfield This is my paper · ORCID
classification cs.DS
keywords datastructurearrayoperationsprefixsierpinskitimetree
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The binary indexed tree, or Fenwick tree, is a data structure that can efficiently update values and calculate prefix sums in an array. It allows both of these operations to be performed in $O(\log_2 N)$ time. Here we present a novel data structure resembling the Sierpinski triangle, which accomplishes these operations with the same memory usage in $O(\log_3 N)$ time instead. We show this order to be optimal by making use of a connection to quantum computing.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Ternary tree transformations are equivalent to linear encodings of the Fock basis

    quant-ph 2024-12 conditional novelty 6.0 of 10

    Every product-preserving ternary tree fermion-qubit mapping is equivalent to a linear encoding of the Fock basis, with an explicit matrix constructed from the tree.

Pith tools