Skip to content

Dynamic Range Sum Queries

  • Title: Dynamic Range Sum Queries
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1648
  • Secondary topics: Point update, Range sum, Iterative segment tree
  • Difficulty: medium
  • Subtype: Support point assignments and online range-sum queries
  • Status: solved
  • Solution file: dynamicrangesumqueries.cpp

Why Practice This

This is one of the best first segment-tree problems because the node state is as simple as possible:

  • each node stores a segment sum
  • updates change one position
  • queries ask for a sum on a range

That makes it a clean place to learn the segment-tree invariant before moving on to minimum queries, descent queries, or lazy propagation.

Recognition Cue

This is a classic online updates + online range queries signal:

  • updates and queries are interleaved
  • one update changes one position
  • each query asks for an aggregate over an interval
  • the merge operation is associative and cheap

That is the segment-tree mental pattern: define a node meaning, define a merge, and support both directions online.

Problem-Specific Transformation

The statement becomes much simpler after one internal rewrite:

  • represent the array with a segment tree whose nodes store segment sums
  • interpret type 1 k u as a point assignment at one leaf
  • interpret type 2 a b as a range-sum query on one-based inclusive [a, b]
  • convert that query into the tree's internal zero-based half-open interval [a - 1, b)

So the problem is not "process custom query syntax." It is "map the judge operations onto one standard point-update/range-query tree."

Core Idea

Store the sum of each segment in a segment tree.

The invariant is:

tree[node] = sum of the array values covered by that node's interval

Then:

  • a point update changes one leaf
  • every ancestor of that leaf is recomputed from its two children
  • a range query is answered by merging the sums of the covered segments

In the iterative version, it is convenient to query on a half-open interval [l, r).

So an input query on one-based inclusive [a, b] becomes:

query(a - 1, b)

after converting to zero-based indexing.

This problem can also be solved with Fenwick, but as a segment-tree ladder anchor it is perfect because the merge is obvious and the implementation pattern is reusable.

Complexity

  • build: O(n)
  • each point update: O(log n)
  • each range query: O(log n)
  • memory: O(n)

Pitfalls / Judge Notes

  • The update sets a[k] = u; it is not an add operation.
  • Use long long for node sums.
  • Be consistent about interval style inside the tree. This solution uses zero-based half-open queries [l, r).
  • Recompute all ancestors after changing one leaf, or later queries will use stale sums.

Reusable Pattern

Solutions