## Table of Contents

Segment TreeResourcesDynamic Range Minimum QueriesRecursive ImplementationIterative ImplementationDynamic Range Sum QueriesRecursive ImplementationIterative ImplementationBinary Indexed TreeResourcesDynamic Range Sum QueriesImplementationFinding the $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeInversion CountingImplementationProblemsGeneralUSACO# Point Update Range Sum

Authors: Benjamin Qi, Dong Liu, Nathan Gong

Contributors: Andrew Wang, Pramana Saldin

Segment Tree, Binary Indexed Tree, and Order Statistic Tree (in C++).

### Prerequisites

## Table of Contents

Segment TreeResourcesDynamic Range Minimum QueriesRecursive ImplementationIterative ImplementationDynamic Range Sum QueriesRecursive ImplementationIterative ImplementationBinary Indexed TreeResourcesDynamic Range Sum QueriesImplementationFinding the $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeInversion CountingImplementationProblemsGeneralUSACOMost 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.

Resources | ||||
---|---|---|---|---|

CF EDU | basic operations, inversion counting | |||

CSA | Interactive updates. | |||

CPH | Same implementation as AICash below. | |||

CPC | See slides after union-find. Also introduces sqrt bucketing. | |||

cp-algo | "Advanced versions" are covered in Platinum. | |||

CF | simple implementation | |||

KACTL | similar to above |

## Dynamic Range Minimum Queries

Focus Problem – try your best to solve this problem before continuing!

### Recursive Implementation

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

C++

#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. */

Java

import java.io.*;import java.util.*;/** A data structure that can answer point update & range min queries. */public class MinSegmentTree {public final int len;private final int[] segtree; // index 0 is not in useprivate int combine(int a, int b) { return Math.min(a, b); }

### 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)$

C++

#include <algorithm>#include <iostream>#include <limits>#include <vector>using std::cout;using std::endl;using std::vector;template <class T> class MinSegmentTree {

Java

import java.io.*;import java.util.*;/** A data structure that can answer point update & range minimum queries. */public class MinSegmentTree {private final int[] segtree;private final int len;public MinSegmentTree(int len) {this.len = len;

Python

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

Focus Problem – try your best to solve this problem before continuing!

### Recursive Implementation

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

C++

Compared to the previous implementation, all we need to change are `DEFAULT`

and how we combine the elements.

#include <algorithm>#include <iostream>#include <limits>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: Segment Tree (Click to expand)

Java

Compared to the previous implementation, all we need to change is
the way we combine the elements, the default value, and the data type
we use for the segment tree (from `int`

to `long`

).

import java.io.*;import java.util.*;public class SumSegmentTree {public final int len;private final long[] segtree;private long combine(long a, long b) { return a + b; }private void build(long[] arr, int at, int atLeft, int atRight) {

### Iterative Implementation

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

C++

#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: Segment Tree (Click to expand)int main() {

Java

import java.io.*;import java.util.*;public class SumSegmentTree {private final long[] segtree;private final int len;public SumSegmentTree(int len) {this.len = len;segtree = new long[len * 2];

Python

Compared to the previous implementation, all we need to change is the way we
aggregate values (from `min()`

to '+'), and change the initial value to 0.

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

Resources | ||||
---|---|---|---|---|

CSA | interactive | |||

CPH | similar to above | |||

cp-algo | also similar to above | |||

TC |

## Dynamic Range Sum Queries

### Implementation

C++

#include <cassert>#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;/*** Short for "binary indexed tree",

Java

import java.io.*;import java.util.*;/*** Short for "binary indexed tree",* this data structure supports point update and range sum* queries like a segement tree.*/public class BIT {private final long[] bit;

Python

class BIT:"""Short for "binary indexed tree",this data structure supports point update and range sumqueries like a segment tree."""def __init__(self, len_: int) -> None:self.bit = [0] * (len_ + 1)self.arr = [0] * len_

# $k$-th Element

Finding theSuppose 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.

Resources | ||||
---|---|---|---|---|

CF | ||||

CPH | brief overview with find_by_order and order_of_key | |||

KACTL | code |

## With a BIT

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

Resources | ||||
---|---|---|---|---|

CF | log N |

## With a Segment Tree

Covered in Platinum.

## Inversion Counting

Focus Problem – try your best to solve this problem before continuing!

### Implementation

C++

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

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

Java

import java.io.*;import java.util.*;public class Main {private static final int MAX_ELEM = (int)1e7;public static void main(String[] args) {Kattio io = new Kattio();int testNum = io.nextInt();for (int t = 0; t < testNum; t++) {

Python

Code Snippet: BIT (Click to expand)MAX_ELEM = 10**7test_num = int(input())for _ in range(test_num):bit = BIT(MAX_ELEM + 1)input()arr_len = int(input())

# Problems

### Coordinate Compression

If the coordinates are large (say, up to $10^9$), then you should apply coordinate compression before using a BIT or segment tree (though sparse segment trees do exist).

## General

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsPURS | |||

Kattis | Easy | ## Show TagsInversions, PURS | |||

CSES | Easy | ## Show TagsPURS | |||

CSES | Easy | ## Show TagsCoordinate Compress, PURS | |||

CF | Easy | ## Show TagsBinary Search, Offline, PURS | |||

CSES | Easy | ## Show TagsCoordinate Compress, PURS | |||

CSES | Normal | ## Show TagsOffline, PURS |

## USACO

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsPURS | |||

Platinum | Easy | ## Show TagsInversions, PURS | |||

Old Gold | Hard | ## Show TagsPURS |

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

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!