Somewhat Frequent

Point Update Range Sum

Authors: Benjamin Qi, Andrew Wang

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(logN)O(\log N) time each on an array of size NN:

  • 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(logN)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.

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


CFsimple implementation
Benqbased off above


1template<class T> struct Seg { // comb(ID,b) = b
2 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 p
7 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) {


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

Binary Indexed Tree

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


CPHsimilar to above
cp-algoalso similar to above



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

Finding kk-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++.

CPHbrief overview with find_by_order and order_of_key

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][1,N].

CF log N

With a Segment Tree

Covered in Platinum.

Example - Inversion Counting

Focus Problem – read through this problem before continuing!



Range Sum Problems


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


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

Module Progress:

Give Us Feedback on Point Update Range Sum!