Point Update Range Sum

Most gold range query problems require you to support following tasks in $\mathcal{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 $\mathcal{O}(\log N)$ time each for any associative operation, not just summation.

Resources

Solution - Range Minimum Queries II

Note that st.init(n+1) allows us to update and query indices in the range [0,n+1)=[0,n].

1#include <bits/stdc++.h>
2using namespace std;
3
4template<class T> struct Seg { // comb(ID,b) = b
5    const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
6    int n; vector<T> seg;
7    void init(int _n) { n = _n; seg.assign(2*n,ID); }
8    void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
9    void upd(int p, T val) { // set val at position p
10        seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }

Solution - Range Sum Queries II

Compared to the previous problem, all we need to change are T, ID, and comb.

1#include <bits/stdc++.h>
2using namespace std;
3
4template<class T> struct Seg { // comb(ID,b) = b
5    const T ID = 0; T comb(T a, T b) { return a+b; }
6    int n; vector<T> seg;
7    void init(int _n) { n = _n; seg.assign(2*n,ID); }
8    void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
9    void upd(int p, T val) { // set val at position p
10        seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }

Binary Indexed Tree

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

Resources

Solution - Range Sum Queries II

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5const int MX = 2e5+5;
6
7int n, q;
8vector<ll> bit(MX), x(MX);
9
10void upd(int i, ll v) {

1/**
2 * Description: range sum queries and point updates for $D$ dimensions
3 * Source: https://codeforces.com/blog/entry/64914
4 * Verification: SPOJ matsum
5 * Usage: \texttt{BIT<int,10,10>} gives 2D BIT
6 * Time: O((\log N)^D)
7 */
8
9template <class T, int ...Ns> struct BIT {
10    T val = 0; void upd(T v) { val += v; }

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.

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

A hint regarding Sleepy Cow Sort: All USACO problems (aside from some special exceptions) have only one possible output.