Segment Tree

A segment tree maintains information about intervals while array entries change. Unlike a Fenwick tree specialized for prefix-like operations, it can combine many associative operations, including sum, minimum, maximum, and greatest common divisor. The array is recursively divided into halves. Each node stores the answer for its entire interval; a range query combines only the nodes needed to cover the requested interval. This lesson implements sums with point assignment. The same structure supports minimum or maximum by changing both the combine operation and the identity value.

Prerequisites: Arrays, recursion, associative operations, range sums.

Build the idea

1. Divide the array, then combine

   The root represents [1,n]. Split [l,r] at m=(l+r)/2 into [l,m] and [m+1,r], until each interval contains one element. Leaves store array values; every internal node stores leftSum+rightSum. For [2,1,3,4,5], the root stores 15, its left child [1,3] stores 6, and its right child [4,5] stores 9. The tree is balanced even when n is not a power of two.

2. Three query cases

   For a requested range [ql,qr], a node interval has no overlap, complete coverage, or partial coverage. Return 0 for no overlap, return the stored sum for complete coverage, and recursively add both children for partial coverage. Returning the identity for no overlap is essential: zero works for sum, but minimum needs positive infinity and maximum needs negative infinity. Complete coverage prevents descending into every element.

3. Why the query stays logarithmic

   At each tree depth, only the two boundary areas of the query can remain partially covered. Nodes strictly inside the requested interval are accepted immediately; outside nodes stop immediately. Therefore the total visited nodes are O(log n), not the number of elements in the range. This reasoning depends on querying one contiguous interval.

4. Change one value

   To set a[i]=x, follow the unique root-to-leaf path containing i, replace that leaf, then recompute each ancestor from its children. Every other node interval excludes i and remains valid. In the sample, sum(2,4)=1+3+4=8; setting a[3]=9 changes it to 14. Point assignment differs from addition and the input command makes that explicit.

5. Implementation boundaries

   The recursive functions carry p, the node's position in the storage array, and l,r, the actual interval. Children are at 2p and 2p+1; these indices are not original array positions. Allocate 4n cells, which comfortably stores this recursive representation. A separate build takes O(n), since every tree node is processed once. This introductory implementation does not support lazy range updates.

6. Boundary cases and operation order

   For n=1, the root is already a leaf: build, assignment, and query each finish immediately. For a range covering the entire array, query returns the root sum immediately. For a single position in a large array, only a logarithmic search path matters. These cases are useful sanity checks when tracing the three query conditions.

   Although addition is commutative, segment trees do not require this property. For string concatenation or matrix multiplication, preserve left-child answer before right-child answer. Associativity permits grouping subintervals differently; it does not permit changing their order.

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

#include<iostream>
#include<vector>
using namespace std;
struct SegmentTree{
    int n;
    vector<long long>tree;
    explicit SegmentTree(const vector<long long>&a):n((int)a.size()-1),tree(4*n+4){
        build(1,1,n,a);
    }
    // p is a storage index; [l,r] is the original array interval.
    void build(int p,int l,int r,const vector<long long>&a){
        if(l==r){
            tree[p]=a[l];
            return;
        }
        int m=l+(r-l)/2;
        build(2*p,l,m,a);
        build(2*p+1,m+1,r,a);
        tree[p]=tree[2*p]+tree[2*p+1];
    }
    // Only one root-to-leaf path contains i; other subtrees remain unchanged.
    void setValue(int p,int l,int r,int i,long long x){
        if(l==r){
            tree[p]=x;
            return;
        }
        int m=l+(r-l)/2;
        if(i<=m){
            setValue(2*p,l,m,i,x);
        }
        else{
            setValue(2*p+1,m+1,r,i,x);
        }
        // Restore the parent aggregate after its changed child returns.
        tree[p]=tree[2*p]+tree[2*p+1];
    }
    long long query(int p,int l,int r,int ql,int qr)const{
        if(qr<l||r<ql){
            return 0; // Identity for addition.
        }
        // A fully covered interval can be answered without inspecting its leaves.
        if(ql<=l&&r<=qr){
            return tree[p];
        }
        int m=l+(r-l)/2;
        return query(2*p,l,m,ql,qr)+query(2*p+1,m+1,r,ql,qr);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<long long>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    SegmentTree st(a);
    while(q--){
        char op;
        cin>>op;
        if(op=='U'){
            int i;
            long long x;
            cin>>i>>x;
            st.setValue(1,1,n,i,x);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<st.query(1,1,n,l,r)<<'\n';
        }
    }
}

Complexity analysis

Build O(n); point assignment O(log n); contiguous range query O(log n); storage O(n), plus O(log n) recursion depth. Associativity is required; commutativity is not required if left-to-right merge order is retained.

Example input and output

n q, n initial values; commands U i x for assignment or S l r for inclusive range sum. n≥1; valid 1-based indices; sums fit long long.

Input

5 3
2 1 3 4 5
S 2 4
U 3 9
S 2 4

Output

8
14

The update assigns 9 to the third element. Both outputs query positions 2 through 4.

Practical applications

Dynamic sums/minima/maxima; HLD path queries; maintaining combined interval information such as maximum subarray sums with a richer node record.

Check your understanding

Which value should a disjoint node return for a minimum query?

Put it into practice

Modify the node information so one query returns sum, minimum, and maximum.