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

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

Dynamic Range Minimum Queries

Recursive Implementation

Time Complexity: $\mathcal{O}((N + Q) \log N)$

Copy
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/** A data structure that can answer point update & range min queries. */

Iterative Implementation

Though less extensible, this implementation is shorter and has a better constant factor. The ranges it operates on are also end-exclusive, unlike the previous one which is end-inclusive.

Time Complexity: $\mathcal{O}((N + Q) \log N)$

Copy
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <class T> class MinSegmentTree {

Dynamic Range Sum Queries

Recursive Implementation

Time Complexity: $\mathcal{O}((N + Q) \log N)$

Compared to the previous implementation, all we need to change are DEFAULT and how we combine the elements.

Copy
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: Segment Tree (Click to expand)

Iterative Implementation

Time Complexity: $\mathcal{O}((N + Q) \log N)$

Copy
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: Segment Tree (Click to expand)

int main() {

Binary Indexed Tree

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

Resources

Dynamic Range Sum Queries

Implementation

Copy
#include <cassert>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/**
 * Short for "binary indexed tree",

Finding the $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++. However, it's only supported on GCC, so Clang users are out of luck.

With a BIT

However, if all updates are in the range $[1,N]$, we can do the same thing with a BIT.

With a Segment Tree

Covered in Platinum.

Inversion Counting

Implementation

Using an indexed set, we can solve this in just a few lines.

Copy
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {

Note that if it were not the case that all elements of the input array were distinct, then this code would be incorrect since Tree<int> would remove duplicates. Instead, we would use an indexed set of pairs (Tree<pair<int,int>>), where the first element of each pair would denote the value while the second would denote the position of the value in the array.

Problems

General

USACO

A hint regarding Sleepy Cow Sort: There is only one correct output.