论文标题
前缀和问题问题的实际权衡
Practical Trade-Offs for the Prefix-Sum Problem
论文作者
论文摘要
给定整数数组a，前缀和前缀问题是回答返回[0..i]中元素总和的总和（i）查询，知道可以更改整数。这是数据结构设计中的一个经典问题，在从编码到数据库的计算中具有广泛的应用程序。在这项工作中，我们提出并比较了这个问题的几种和实用的解决方案，表明查询性能和更新之间的新权衡可以实现现代硬件。
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.
