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
import math
from typing import List, Optional


class MinSegmentTree:
	def __init__(self, arr: Optional[List[int]] = None, length: Optional[int] = None):
		self.DEFAULT = math.inf
		if arr is None:
			self.n = length
			self.segtree = [self.DEFAULT] * (self.n * 4)

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
class MinSegmentTree:
	"""A data structure that can answer point update & range minimum queries."""

	def __init__(self, len_: int):
		self.len = len_
		self.tree = [0] * (2 * len_)

	def set(self, ind: int, val: int) -> None:
		"""Sets the value at ind to val."""
		ind += self.len

Dynamic Range Sum Queries

Recursive Implementation

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

Copy
from typing import List, Optional


class SumSegmentTree:
	def __init__(self, arr: Optional[List[int]] = None, length: Optional[int] = None):
		self.DEFAULT = 0
		if arr is None:
			self.n = length
			self.segtree = [self.DEFAULT] * (self.n * 4)
		else:

Iterative Implementation

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

Copy
 Code Snippet: Segment Tree (Click to expand)


arr_len, query_num = map(int, input().split())
arr = list(map(int, input().split()))

segtree = SumSegmentTree(arr_len)
for i, v in enumerate(arr):
	segtree.set(i, v)

Binary Indexed Tree

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

Resources

Dynamic Range Sum Queries

Implementation

Copy
class BIT:
	"""
	Short for "binary indexed tree",
	this data structure supports point update and range sum
	queries like a segment tree.
	"""

	def __init__(self, len_: int) -> None:
		self.bit = [0] * (len_ + 1)
		self.arr = [0] * len_

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

Copy
 Code Snippet: BIT (Click to expand)

MAX_ELEM = 10**7

test_num = int(input())
for _ in range(test_num):
	bit = BIT(MAX_ELEM + 1)

	input()
	arr_len = int(input())

Problems

General

USACO