Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Created August 13, 2023 11:54
Show Gist options
  • Save Phryxia/b493e373f2610bf054f8e11f3404c105 to your computer and use it in GitHub Desktop.
Save Phryxia/b493e373f2610bf054f8e11f3404c105 to your computer and use it in GitHub Desktop.
TypeScript implementation of fast cumulative sum
class CumulativeSum {
private sums: number[] = [0];
constructor(itr: Iterable<number>) {
const values = [...itr];
for (let i = 0; i < values.length; ++i) {
this.sums[i + 1] = this.sums[i] + values[i];
}
}
get(from: number, to: number) {
if (to < 0) return 0;
from = Math.max(from, 0);
to = Math.min(to, this.sums.length - 2);
return this.sums[to + 1] - this.sums[from];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment