Point Update Range Sum

C++

Note that st.init(n+1) allows us to update and query indices in the range [0,n+1)=[0,n].

Copy
#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); }

Java

Copy
import java.util.*;
import java.io.*;

public class DynamicRangeMinQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();

		SegmentTree seg = new SegmentTree(n);

C++

Compared to the previous problem, all we need to change are T, ID, and comb.

Copy
#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); }

Java

Compared to the previous problem, all we need to change is the way we aggregate values (change from Math.min() to summation) and the data type we use to store the query (int to long).

Copy
import java.util.*;
import java.io.*;

public class DynamicRangeSumQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();

		SegmentTree seg = new SegmentTree(n);

C++

Solution 1

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

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

Java

Copy
import java.util.*;
import java.io.*;

public class DynamicRangeSumQueries {
	static long[] bit;
	static int n;
	public static void main(String[] args) {
		Kattio io = new Kattio();
		n = io.nextInt();
		int q = io.nextInt();