PrevNext
Somewhat Frequent
 0/15

Point Update Range Sum

Authors: Benjamin Qi, Andrew Wang, Dong Liu

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

Focus Problem – read through this problem before continuing!


Most gold range query problems require you to support following tasks in O(logN)\mathcal{O}(\log N) time each on an array of size NN:

  • 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 O(logN)\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
CFbasic operations, inversion counting
CSAInteractive updates.
CPHSame implementation as AICash below.
CPCSee slides after union-find. Also introduces sqrt bucketing.
cp-algo"Advanced versions" are covered in Platinum.

Solution - Range Minimum Queries II

Resources
CFsimple implementation
Benqbased 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) = b
const 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 p
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.

C++

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

Resources
CSAinteractive
CPHsimilar to above
cp-algoalso 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.

/**
* 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; }

Finding kk-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++.

Resources
CF
CPHbrief overview with find_by_order and order_of_key
Benqcode

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

With a BIT

Assumes all updates are in the range [1,N][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 10910^9), then you should apply coordinate compression before using a BIT or segment tree (though sparse segment trees do exist).

General

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

PURS

KattisEasy
Show Tags

PURS, Inversions

CSESEasy
Show Tags

PURS

CSESEasy
Show Tags

PURS, Coordinate Compress

CSESEasy
Show Tags

PURS, Coordinate Compress

CSESNormal
Show Tags

PURS, Offline

USACO

StatusSourceProblem NameDifficultyTagsSolutionURL
GoldEasy
Show Tags

PURS, Inversions

GoldEasy
Show Tags

PURS, Inversions

External Sol
GoldEasy
Show Tags

PURS, Inversions

External Sol
GoldEasy
Show Tags

PURS

External Sol
PlatEasy
Show Tags

PURS, Inversions

External Sol
Old GoldHard
Show Tags

PURS

External Sol

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!

Give Us Feedback on Point Update Range Sum!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext