PrevNext
Somewhat Frequent
 0/15

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.

Resources

Pro Tip

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

Resources
CSAInteractive updates.
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) = 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) {

Java

1import java.util.*;
2import java.io.*;
3
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(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

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

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][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

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

Module Progress:

Give Us Feedback on Point Update Range Sum!

PrevNext