Square Root Decomposition

Square root decomposition partitions an array into blocks and stores a summary for each block. A range query consumes whole blocks quickly and examines only the partial blocks at its ends. This lesson supports point assignments and inclusive range sums. It is a useful middle ground between scanning everything and implementing a tree, and a foundation for more specialized block-based data structures.

Prerequisites: Arrays; prefix sums; arithmetic on indices. Difficulty: Advanced.

Build the idea

1. 1. Choose a block invariant

   Let B≈√n. Position i belongs to block (i−1)/B under 1-based indexing. Store block[b] as the exact sum of all array elements belonging to b. The final block may be shorter. Building summaries requires one pass, and the array itself remains available for boundary positions and update deltas. The number of blocks is ceil(n/B), not always exactly B.

2. 2. Answer with full blocks and tails

   At a current position l, use a block sum only when l is its first position and the entire B-position block fits before r. Otherwise add a[l] and advance one position. This loop naturally handles short ranges and the final incomplete block. At most two partial blocks are scanned, and at most n/B full-block summaries are consumed.

3. 3. Update by a difference

   For an assignment a[i]=value, add value−oldValue to its block sum, then replace the stored element. The sum summary supports this O(1) correction. This does not generalize automatically to every aggregate: a block minimum may need an O(B) rebuild if the old minimum is removed. State the update cost for the chosen summary, rather than claiming all block structures behave identically.

4. 4. Work through the sample

   For n=5 this code chooses B=2. Initial blocks are [1,2] with sum 3, [3,4] with sum 7, and [5] with sum 5. Query [2,5] takes a[2]=2, full block [3,4]=7, and a[5]=5, returning 14. Assigning position 3 to 10 increases the second block by 7, making its sum 14. Query [1,3] then returns block 0 sum 3 plus a[3]=10, or 13.

   Block	Indices	Initial sum	After U 3 10
   0	1..2	3	3
   1	3..4	7	14
   2	5	5	5

5. 5. Balance the two sources of work

   A query does O(B+n/B) work: scanning boundary elements costs O(B), while whole blocks cost O(n/B). This expression is minimized around √n. Constants and operation mix may suggest another block size. Here point updates remain O(1) for any B. Block decomposition is flexible, but for sums alone Fenwick usually offers faster asymptotic operations with a similarly compact implementation.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
using ll=long long;
int main(){
    int n,q;
    if(!(cin>>n>>q)){
        return 0;
    }
    int B=max(1,(int)sqrt(n));
    vector<ll>a(n+1),block((n+B-1)/B,0);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        block[(i-1)/B]+=a[i];
    }
    while(q--){
        char type;
        cin>>type;
        if(type=='U'){
            int i;
            ll value;
            cin>>i>>value;
            block[(i-1)/B]+=value-a[i];
            a[i]=value; // Point assignment.
        }
        else{
            int l,r;
            cin>>l>>r;
            ll answer=0;
            while(l<=r){
                if((l-1)%B==0&&l+B-1<=r){
                    answer+=block[(l-1)/B];
                    l+=B;
                }
                else{
                    answer+=a[l++];
                }
            }
            cout<<answer<<'\n';
        }
    }
}

Complexity analysis

O(n) preprocessing, O(1) point assignment, O(B+n/B)=O(√n) range sum query with B≈√n, and O(n) memory including array plus O(n/B) summaries. A minimum-based block variant might instead need O(B) updates; that is not the sum variant taught here. n≤200000 and |values|≤10^9 keep all sums within long long.

Example input and output

Read n q (1≤n≤200000), then n integers. Each operation is U i value (assign) or Q l r (inclusive sum), with valid positions and l≤r. Print one line per Q.

Input

5 4
1 2 3 4 5
Q 2 5
U 3 10
Q 1 3
Q 3 3

Output

14
13
10

The update replaces 3 by 10; later range sums use the changed block summary and array value.

Practical applications

Use for simple range data with custom per-block summaries, rebuilding tricks and situations where √n performance is sufficient. Fenwick supports dynamic sums in O(log n); a segment tree handles many associative aggregates. Mo also uses √n-scale organization, but reorders offline queries instead of storing a directly queryable array summary.

Check your understanding

Why is a point sum update O(1) here?

Put it into practice

Adapt the structure to range minimum with point assignments.