Somewhat Frequent
0/15

# Point Update Range Sum

Authors: Benjamin Qi, Andrew Wang

### Prerequisites

Introduces Segment Tree, Binary Indexed Tree, and Order Statistic Tree (C++ only).

Focus Problem – read through this problem before continuing!

Most gold range query problems require you to support following tasks in $O(\log N)$ time each on an array of size $N$:

• Update the element at a single position (point).
• Query the sum of some consecutive subarray.

Both segment trees and binary indexed trees can accomplish this.

## Segment Tree

Focus Problem – read through this problem before continuing!

A segment tree allows you to do point update and range query in $O(\log N)$ time each for any associative operation, not just summation.

### Pro Tip

You can skip more advanced applications such as lazy propagation for now. They will be covered in platinum.

Resources
CPHSame implementation as AICash below.
CPCSee slides after union-find. Also introduces sqrt bucketing.
cp-algoAdvanced versions will be covered in Plat.

### Implementations

Resources
CFsimple implementation
Benqbased off above

C++

1template<class T> struct Seg { // comb(ID,b) = b2    const T ID = 0; T comb(T a, T b) { return a+b; }3    int n; vector<T> seg;4    void init(int _n) { n = _n; seg.assign(2*n,ID); }5    void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }6    void upd(int p, T val) { // set val at position p7        seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }8    T query(int l, int r) { // sum on interval [l, r]9        T ra = ID, rb = ID;10        for (l += n, r += n+1; l < r; l /= 2, r /= 2) {

Java

1import java.util.*;2import java.io.*;3
4public class segtree {5    public static final int N = (int) 1e5; // limit for array size6    public static int n; // array size7    public static long t[] = new long[2 * N];8    public static void main(String[] args) throws Exception {9        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));10        n = Integer.parseInt(br.readLine());

## Binary Indexed Tree

Implementation is shorter than segment tree, but maybe more confusing at first glance.

### Resources

Resources
CSAinteractive
CPHsimilar to above
cp-algoalso similar to above
TC

### Implementations

C++

Resources
CF
Benqbased off above

Java

1public static long[] fwt;2public static long query(int a, int b) {3    return sum(b) - sum(a - 1);4}5public static long sum(int i) {6    long sum = 0;7    while (i > 0) {8        sum += fwt[i];9        i -= (i & -i); //least important bit10    }

## Finding $k$-th Element

Suppose that we want a data structure that supports all the operations as a set in C++ in addition to the following:

• order_of_key(x): counts the number of elements in the set that are strictly less than x.
• find_by_order(k): similar to find, returns the iterator corresponding to the k-th lowest element in the set (0-indexed).

### Order Statistic Tree

Luckily, such a built-in data structure already exists in C++.

Resources
CF
CPHbrief overview with find_by_order and order_of_key
Benqcode

To use indexed set locally, you need to install GCC as mentioned in Running Code.

### With a BIT

Assumes all updates are in the range $[1,N]$.

Resources
CF log N

### With a Segment Tree

Covered in Platinum.

## Example - Inversion Counting

Focus Problem – read through this problem before continuing!

Solution

## Range Sum Problems

### General

StatusSourceProblem NameDifficultyTagsSolution
CSESEasyShow Sketch
CSESEasyShow Sketch
CSESEasyShow Sketch
CSESEasyView Solution
KattisEasyShow Sketch
CSESNormalShow Sketch

### USACO

Haircut, Balanced Photo, and Circle Cross are just variations on inversion counting.

StatusSourceProblem NameDifficultyTagsSolution
GoldEasyExternal Sol
GoldEasyExternal Sol
GoldEasyExternal Sol
GoldEasyExternal Sol
PlatEasyExternal Sol
Old GoldHardExternal Sol