## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Range Sum Queries IISolution 1Solution 2Finding $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACOEdit this page# Point Update Range Sum

Authors: Benjamin Qi, Andrew Wang, Dong Liu

### Prerequisites

Introduces Segment Tree, Binary Indexed Tree, and C++ Order Statistic Tree.

## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Range Sum Queries IISolution 1Solution 2Finding $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACOEdit this page

Focus Problem – read through this problem before continuing!

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

Focus Problem – read through this problem before continuing!

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

### Pro Tip

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

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

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

### Solution - Dynamic Range Minimum Queries

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

CF | simple implementation | ||

Benq | based off above |

Note that `st.init(n+1)`

allows us to update and query indices in the range
`[0,n+1)=[0,n]`

.

C++

#include <bits/stdc++.h>using namespace std;template<class T> struct Seg { // comb(ID,b) = bconst T ID = 1e18; T comb(T a, T b) { return min(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 pseg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }

### Solution - Dynamic Range Sum Queries

Compared to the previous problem, all we need to change are `T`

, `ID`

, and
`comb`

.

C++

#include <bits/stdc++.h>using namespace std;template<class T> struct Seg { // comb(ID,b) = bconst 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 pseg[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

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

CSA | interactive | ||

CPH | similar to above | ||

cp-algo | also similar to above | ||

TC |

### Solution - Range Sum Queries II

C++

#### Solution 1

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

#### Solution 2

Writing a BIT this way has the advantage of generalizing to multiple dimensions.

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

CF | |||

Benq | based off above |

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

## $k$-th Element

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

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

CF | |||

CPH | brief overview with find_by_order and order_of_key | ||

Benq | code |

To use indexed set locally, you need to install GCC.

### With a BIT

Assumes all updates are in the range $[1,N]$.

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

CF | log N |

### With a Segment Tree

Covered in Platinum.

## Example - Inversion Counting

Focus Problem – read through this problem before continuing!

### Solution

Solution

## Range Sum 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 | |||||||

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

Plat | Easy | ## Show TagsInversions, PURS | |||||||

Old Gold | Hard | ## Show TagsPURS | |||||||

A hint regarding Sleepy Cow Sort: All USACO problems (aside from some special exceptions) have only one possible 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!