Skip to the editor
JSGroundwork
JSGroundwork handwritten · web dev
←Back to Segment & Fenwick trees

Ready to read

JSJavaScript⑂Git◎Interview prepΣDSA in JSSDSystem Design
More topics15›
</>HTML{ }CSS⚛ReactNNext.jsNeNest.jsTSTypeScriptNoNode.js🐳DockerDBSQL & Databases✓Testing🔒Web Security☁Cloud & DevOps◈GraphQL◆Redis☸Kubernetes
☰‹›
Description
All topics›JavaScript›Segment & Fenwick trees

Range Sum Query — Mutable

advancedlayer A6 · Segment & Fenwick trees5 tests

Build a NumArray class over an integer array that supports point updates and range-sum queries.

  • new NumArray(nums) — takes a copy of the array
  • update(i, val) — replaces the value at index i with val (it is not a delta)
  • sumRange(l, r) — the sum of indices l through r inclusive, with 0 <= l <= r < nums.length
  • Both update and sumRange must run in O(log n). Re-summing the slice on every query, or rebuilding prefix sums on every update, is not acceptable — the tests interleave thousands of both
  • Values may be negative

Stuck?

All exercisesPlayground
1234567891011121314
loading the editor…

Nothing yet — hit Run and whatever you log shows up here.

Submit to see how you did.

⌘/Ctrl + Enter run⌘/Ctrl + S save⌘/Ctrl + / comment⌘/Ctrl + F find/replace⌘/Ctrl + D select next matchAlt + click multi-cursorTab indent · ⇧Tab outdentEsc leave fullscreen