segment_tree_static.cpp

#include <bits/stdc++.h>

using namespace std;

// This is an example of segment tree that calculates and updates the
// sum of values of any contiguous segment in an array in O(log(n)).

// Other problems solved by the segment trees have similar code
// with some modifications.

#define childL(id) (id * 2)
#define childR(id) (id * 2 + 1)

const int N = 100100;

int n, a[N];
int tree[N * 4];
int lazy[N * 4];

// Updates a specific node by the given values.
int updateNode(int v, int id, int l, int r) {
	lazy[id] += v;
	tree[id] += (r - l) * v;
	return tree[id];
}

// Propagates the lazy updated data of the given node down to its children.
void propagate(int id, int l, int r) {
	int mid = (l + r) / 2;

	updateNode(lazy[id], childL(id), l, mid);
	updateNode(lazy[id], childR(id), mid, r);

	lazy[id] = 0;
}

// Builds the segment tree recursively.
// O(n)
int build(int id = 1, int l = 0, int r = n) {
	if (l == r - 1) return tree[id] = a[l];

	int mid = (l + r) / 2;

	return tree[id] = build(childL(id), l, mid) + build(childR(id), mid, r);
}

// Updates the range define by [x, y) by the given value v.
// O(log(n))
int update(int x, int y, int v, int id = 1, int l = 0, int r = n) {
	if (x >= r || y <= l) return tree[id];
	if (x <= l && y >= r) return updateNode(v, id, l, r);

	propagate(id, l, r);

	int mid = (l + r) / 2;

	return tree[id] = update(x, y, v, childL(id), l, mid) + update(x, y, v, childR(id), mid, r);
}

// Queries the segment tree to return the value of the range define by [x, y).
// O(log(n))
int query(int x, int y, int id = 1, int l = 0, int r = n) {
	if (x >= r || y <= l) return 0;
	if (x <= l && y >= r) return tree[id];

	propagate(id, l, r);

	int mid = (l + r) / 2;

	return query(x, y, childL(id), l, mid) + query(x, y, childR(id), mid, r);
}