Point Update Range Sum

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

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.

Resources

Implementations

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

import java.util.*;
import java.io.*;

public class segtree {
   public static final int N = (int)1e5;  // limit for array size
   public static int n;  // array size
   public static long t[] = new long[2*N]; 
   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());

Binary Indexed Tree

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

Resources

Implementations

public static long[] fwt;
public static long query(int a, int b)
{
   return sum(b) - sum(a - 1);
}
public static long sum(int i)
{
   long sum = 0;
   while(i > 0){
      sum += fwt[i];

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

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]$.

With a Segment Tree

Covered in Platinum.

Example - Inversion Counting

Solution

Range Sum Problems

General

USACO

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

Segment Tree Problems

So far, no Gold problem has required a segment tree.