# Practical Trade-Offs for the Prefix-Sum Problem

arXiv: https://arxiv.org/abs/2006.14552 · HTML: https://mlsanity.com/paper/2006.14552/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)

## Abstract (arXiv)

Given an integer array A, the prefix-sum problem is to answer sum(i) queries that return the sum of the elements in A[0..i], knowing that the integers in A can be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare several and practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.