Actualización puntual y suma de rango

La mayoría de los problemas de consultas de rango de Oro piden soportar las siguientes tareas en tiempo $\mathcal{O}(\log N)$ cada una sobre un arreglo de tamaño $N$ :

Actualizar el elemento en una sola posición (punto).
Consultar la suma de algún subarreglo consecutivo.

Tanto los árboles de segmentos como los árboles de Fenwick (binary indexed trees) pueden hacer esto.

Árbol de Segmentos

Un árbol de segmentos (segment tree) permite hacer actualización puntual y consulta de rango en tiempo $\mathcal{O}(\log N)$ cada una para cualquier operación asociativa, no solo la suma.

Recursos

Por ahora se pueden saltear las aplicaciones más avanzadas como la propagación perezosa (lazy propagation). Se cubren en Platino.

Recursos
Fuente	Recurso	Notas
CF EDU	Segment Tree Pt 1 Steps 1, 3, 4	operaciones básicas, conteo de inversiones
CSA	Segment Trees	Actualizaciones interactivas.
CPH	9.3 - Segment Trees	Misma implementación que AICash más abajo.
CPC	3 - Data Structures	Ver las diapositivas después de union-find. También introduce el bucketing por raíz cuadrada.
cp-algo	Simplest form of a Segment Tree	Las “versiones avanzadas” se cubren en Platino.
CF	AICash - Efficient and easy segment trees	implementación simple
KACTL	Segment Tree	similar a la de arriba

Dynamic Range Minimum Queries

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Dynamic Range Minimum Queries	Fácil	PURQ	en el módulo

Implementación recursiva

Complejidad temporal: $\mathcal{O}((N + Q) \log N)$

C++JavaPython


#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. */
template <class T> class MinSegmentTree {
  private:
	const T DEFAULT = std::numeric_limits<T>().max();
 
	int len;
	vector<T> segtree;  // index 0 is not in use
 
	T combine(const T &a, const T &b) { return std::min(a, b); }
 
	void build(const vector<T> &arr, int at, int at_left, int at_right) {
		if (at_left == at_right) {
			segtree[at] = arr[at_left];
			return;
		}
		int mid = (at_left + at_right) / 2;
		build(arr, 2 * at, at_left, mid);
		build(arr, 2 * at + 1, mid + 1, at_right);
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	void set(int ind, T val, int at, int at_left, int at_right) {
		if (at_left == at_right) {
			segtree[at] = val;
			return;
		}
		int mid = (at_left + at_right) / 2;
		if (ind <= mid) {
			set(ind, val, 2 * at, at_left, mid);
		} else {
			set(ind, val, 2 * at + 1, mid + 1, at_right);
		}
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	T range_min(int start, int end, int at, int at_left, int at_right) {
		if (at_right < start || end < at_left) { return DEFAULT; }
		if (start <= at_left && at_right <= end) { return segtree[at]; }
		int mid = (at_left + at_right) / 2;
		T left_res = range_min(start, end, 2 * at, at_left, mid);
		T right_res = range_min(start, end, 2 * at + 1, mid + 1, at_right);
		return combine(left_res, right_res);
	}
 
  public:
	MinSegmentTree(int len) : len(len) { segtree = vector<T>(len * 4, DEFAULT); };
 
	MinSegmentTree(const vector<T> &arr) : len(arr.size()) {
		segtree = vector<T>(len * 4, DEFAULT);
		build(arr, 1, 0, len - 1);
	}
 
	/** Sets the value at ind to val. */
	void set(int ind, T val) { set(ind, val, 1, 0, len - 1); }
 
	/** @return the minimum element in the range [start, end] */
	T range_min(int start, int end) { return range_min(start, end, 1, 0, len - 1); }
};
 
int main() {
	int arr_len;
	int query_num;
	std::cin >> arr_len >> query_num;
	vector<long long> arr(arr_len);
	for (long long &i : arr) { std::cin >> i; }
 
	MinSegmentTree<long long> segtree(arr);
	for (int q = 0; q < query_num; q++) {
		int type;
		std::cin >> type;
		if (type == 1) {
			int ind, val;
			std::cin >> ind >> val;
			segtree.set(ind - 1, val);
		} else if (type == 2) {
			int start, end;
			std::cin >> start >> end;
			cout << segtree.range_min(start - 1, end - 1) << '\n';
		}
	}
}


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 use
 
	private int combine(int a, int b) { return Math.min(a, b); }
 
	private void build(int[] arr, int at, int atLeft, int atRight) {
		if (atLeft == atRight) {
			segtree[at] = arr[atLeft];
			return;
		}
		int mid = (atLeft + atRight) / 2;
		build(arr, 2 * at, atLeft, mid);
		build(arr, 2 * at + 1, mid + 1, atRight);
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	private void set(int ind, int val, int at, int atLeft, int atRight) {
		if (atLeft == atRight) {
			segtree[at] = val;
			return;
		}
		int mid = (atLeft + atRight) / 2;
		if (ind <= mid) {
			set(ind, val, 2 * at, atLeft, mid);
		} else {
			set(ind, val, 2 * at + 1, mid + 1, atRight);
		}
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	private int rangeMin(int start, int end, int at, int atLeft, int atRight) {
		if (atRight < start || end < atLeft) { return Integer.MAX_VALUE; }
		if (start <= atLeft && atRight <= end) { return segtree[at]; }
		int mid = (atLeft + atRight) / 2;
		int leftRes = rangeMin(start, end, 2 * at, atLeft, mid);
		int rightRes = rangeMin(start, end, 2 * at + 1, mid + 1, atRight);
		return combine(leftRes, rightRes);
	}
 
	/** Sets the value at ind to val. */
	void set(int ind, int val) { set(ind, val, 1, 0, len - 1); }
 
	/** @return the minimum element in the range [start, end] */
	int rangeMin(int start, int end) { return rangeMin(start, end, 1, 0, len - 1); }
 
	public MinSegmentTree(int len) {
		this.len = len;
		segtree = new int[len * 4];
		Arrays.fill(segtree, Integer.MAX_VALUE);
	}
 
	public MinSegmentTree(int[] arr) {
		this.len = arr.length;
		segtree = new int[len * 4];
		build(arr, 1, 0, len - 1);
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int arrLen = io.nextInt();
		int queryNum = io.nextInt();
 
		int[] arr = new int[arrLen];
		for (int i = 0; i < arrLen; i++) { arr[i] = io.nextInt(); }
		MinSegmentTree segtree = new MinSegmentTree(arr);
 
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int arg1 = io.nextInt();
			int arg2 = io.nextInt();
			if (type == 1) {
				segtree.set(arg1 - 1, arg2);
			} else {
				io.println(segtree.rangeMin(arg1 - 1, arg2 - 1));
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import math
from typing import List, Optional
 
 
class MinSegmentTree:
	def __init__(self, arr: Optional[List[int]] = None, length: Optional[int] = None):
		self.DEFAULT = math.inf
		if arr is None:
			self.n = length
			self.segtree = [self.DEFAULT] * (self.n * 4)
		else:
			self.n = len(arr)
			self.segtree = [self.DEFAULT] * (self.n * 4)
			self._build(arr, 1, 0, self.n - 1)
 
	def _combine(self, a: int, b: int) -> int:
		return min(a, b)
 
	def _build(self, arr: List[int], at: int, at_left: int, at_right: int) -> None:
		if at_left == at_right:
			self.segtree[at] = arr[at_left]
			return
		mid = (at_left + at_right) // 2
		self._build(arr, at * 2, at_left, mid)
		self._build(arr, at * 2 + 1, mid + 1, at_right)
		self.segtree[at] = self._combine(self.segtree[at * 2], self.segtree[at * 2 + 1])
 
	def _set(self, ind: int, val: int, at: int, at_left: int, at_right: int) -> None:
		if at_left == at_right:
			self.segtree[at] = val
			return
		mid = (at_left + at_right) // 2
		if ind <= mid:
			self._set(ind, val, at * 2, at_left, mid)
		else:
			self._set(ind, val, at * 2 + 1, mid + 1, at_right)
		self.segtree[at] = self._combine(self.segtree[at * 2], self.segtree[at * 2 + 1])
 
	def set(self, ind: int, val: int) -> None:
		if self.n == 0:
			return
		self._set(ind, val, 1, 0, self.n - 1)
 
	def _range_min(
		self, start: int, end: int, at: int, at_left: int, at_right: int
	) -> int:
		if at_right < start or end < at_left:
			return self.DEFAULT
		if start <= at_left and at_right <= end:
			return self.segtree[at]
		mid = (at_left + at_right) // 2
		left_res = self._range_min(start, end, at * 2, at_left, mid)
		right_res = self._range_min(start, end, at * 2 + 1, mid + 1, at_right)
		return self._combine(left_res, right_res)
 
	def range_min(self, start: int, end: int) -> int:
		if self.n == 0:
			return self.DEFAULT
		return self._range_min(start, end, 1, 0, self.n - 1)
 
 
arr_len, query_num = map(int, input().split())
arr = list(map(int, input().split()))
segtree = MinSegmentTree(arr=arr)
 
out = []
for _ in range(query_num):
	t, a, b = map(int, input().split())
	if t == 1:
		segtree.set(a - 1, b)
	else:
		out.append(str(segtree.range_min(a - 1, b - 1)))
 
print("\n".join(out))

Implementación iterativa

Aunque es menos extensible, esta implementación es más corta y tiene un mejor factor constante. Los rangos sobre los que opera también son exclusivos en el extremo derecho, a diferencia de la anterior, que es inclusiva en ambos extremos.

Complejidad temporal: $\mathcal{O}((N + Q) \log N)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
template <class T> class MinSegmentTree {
  private:
	const T DEFAULT = std::numeric_limits<T>().max();
 
	vector<T> segtree;
	int len;
 
  public:
	MinSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = std::min(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	T range_min(int start, int end) {
		T min = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { min = std::min(min, segtree[start++]); }
			if (end % 2 == 1) { min = std::min(min, segtree[--end]); }
		}
		return min;
	}
};
 
int main() {
	int arr_len;
	int query_num;
	std::cin >> arr_len >> query_num;
 
	MinSegmentTree<int> segtree(arr_len);
	for (int i = 0; i < arr_len; i++) {
		int n;
		std::cin >> n;
		segtree.set(i, n);
	}
 
	for (int q = 0; q < query_num; q++) {
		int type, arg1, arg2;
		std::cin >> type >> arg1 >> arg2;
		if (type == 1) {
			segtree.set(arg1 - 1, arg2);
		} else if (type == 2) {
			cout << segtree.range_min(arg1 - 1, arg2) << '\n';
		}
	}
}


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;
		segtree = new int[len * 2];
		Arrays.fill(segtree, Integer.MAX_VALUE);
	}
 
	/** Sets the value at ind to val. */
	public void set(int ind, int val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = Math.min(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	/** @return the minimum of all elements in [start, end). */
	public int rangeMin(int start, int end) {
		int min = Integer.MAX_VALUE;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { min = Math.min(min, segtree[start++]); }
			if (end % 2 == 1) { min = Math.min(min, segtree[--end]); }
		}
		return min;
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int arrLen = io.nextInt();
		int queryNum = io.nextInt();
 
		MinSegmentTree segtree = new MinSegmentTree(arrLen);
		for (int i = 0; i < arrLen; i++) { segtree.set(i, io.nextInt()); }
 
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int arg1 = io.nextInt();
			int arg2 = io.nextInt();
			if (type == 1) {
				segtree.set(arg1 - 1, arg2);
			} else {
				io.println(segtree.rangeMin(arg1 - 1, arg2));
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


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
		self.tree[ind] = val
 
		while ind > 1:
			self.tree[ind // 2] = min(self.tree[ind], self.tree[ind ^ 1])
			ind //= 2
 
	def range_min(self, start: int, end: int) -> int:
		""":return: the minimum element of all elements in [start, end)"""
		start += self.len
		end += self.len
		min_ = float("inf")
		while start < end:
			if start % 2 == 1:
				min_ = min(min_, self.tree[start])
				start += 1
			if end % 2 == 1:
				end -= 1
				min_ = min(min_, self.tree[end])
 
			start //= 2
			end //= 2
		return min_
 
 
arr_len, query_num = map(int, input().split())
arr = list(map(int, input().split()))
 
segtree = MinSegmentTree(arr_len)
for i, v in enumerate(arr):
	segtree.set(i, v)
 
for _ in range(query_num):
	type_, arg1, arg2 = map(int, input().split())
	if type_ == 1:
		segtree.set(arg1 - 1, arg2)
	elif type_ == 2:
		print(segtree.range_min(arg1 - 1, arg2))

Dynamic Range Sum Queries

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Dynamic Range Sum Queries	Fácil	PURS	en el módulo

Implementación recursiva

Complejidad temporal: $\mathcal{O}((N + Q) \log N)$

C++JavaPython

Comparado con la implementación anterior, lo único que hay que cambiar es DEFAULT y cómo combinamos los elementos.


#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{Segment Tree}
template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;
 
	int len;
	vector<T> segtree;
 
	T combine(const T &a, const T &b) { return a + b; }
 
	void build(const vector<T> &arr, int at, int at_left, int at_right) {
		if (at_left == at_right) {
			segtree[at] = arr[at_left];
			return;
		}
		int mid = (at_left + at_right) / 2;
		build(arr, 2 * at, at_left, mid);
		build(arr, 2 * at + 1, mid + 1, at_right);
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	void set(int ind, T val, int at, int at_left, int at_right) {
		if (at_left == at_right) {
			segtree[at] = val;
			return;
		}
		int mid = (at_left + at_right) / 2;
		if (ind <= mid) {
			set(ind, val, 2 * at, at_left, mid);
		} else {
			set(ind, val, 2 * at + 1, mid + 1, at_right);
		}
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	T range_sum(int start, int end, int at, int at_left, int at_right) {
		if (at_right < start || end < at_left) { return DEFAULT; }
		if (start <= at_left && at_right <= end) { return segtree[at]; }
		int mid = (at_left + at_right) / 2;
		T left_res = range_sum(start, end, 2 * at, at_left, mid);
		T right_res = range_sum(start, end, 2 * at + 1, mid + 1, at_right);
		return combine(left_res, right_res);
	}
 
  public:
	SumSegmentTree(int len) : len(len) { segtree = vector<T>(len * 4, DEFAULT); };
 
	SumSegmentTree(const vector<T> &arr) : len(arr.size()) {
		segtree = vector<T>(len * 4, DEFAULT);
		build(arr, 1, 0, len - 1);
	}
 
	void set(int ind, T val) { set(ind, val, 1, 0, len - 1); }
 
	T range_sum(int start, int end) { return range_sum(start, end, 1, 0, len - 1); }
};
// EndCodeSnip
 
int main() {
	int arr_len;
	int query_num;
	std::cin >> arr_len >> query_num;
	vector<long long> arr(arr_len);
	for (long long &i : arr) { std::cin >> i; }
 
	SumSegmentTree<long long> segtree(arr);
	for (int q = 0; q < query_num; q++) {
		int type;
		std::cin >> type;
		if (type == 1) {
			int ind, val;
			std::cin >> ind >> val;
			segtree.set(ind - 1, val);
		} else if (type == 2) {
			int start, end;
			std::cin >> start >> end;
			cout << segtree.range_sum(start - 1, end - 1) << '\n';
		}
	}
}

Comparado con la implementación anterior, lo único que hay que cambiar es la forma de combinar los elementos, el valor por defecto y el tipo de datos que usamos para el árbol de segmentos (de int a 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) {
		if (atLeft == atRight) {
			segtree[at] = arr[atLeft];
			return;
		}
		int mid = (atLeft + atRight) / 2;
		build(arr, 2 * at, atLeft, mid);
		build(arr, 2 * at + 1, mid + 1, atRight);
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	private void set(int ind, long val, int at, int atLeft, int atRight) {
		if (atLeft == atRight) {
			segtree[at] = val;
			return;
		}
		int mid = (atLeft + atRight) / 2;
		if (ind <= mid) {
			set(ind, val, 2 * at, atLeft, mid);
		} else {
			set(ind, val, 2 * at + 1, mid + 1, atRight);
		}
		segtree[at] = combine(segtree[2 * at], segtree[2 * at + 1]);
	}
 
	private long rangeSum(int start, int end, int at, int atLeft, int atRight) {
		if (atRight < start || end < atLeft) { return 0; }
		if (start <= atLeft && atRight <= end) { return segtree[at]; }
		int mid = (atLeft + atRight) / 2;
		long leftRes = rangeSum(start, end, 2 * at, atLeft, mid);
		long rightRes = rangeSum(start, end, 2 * at + 1, mid + 1, atRight);
		return combine(leftRes, rightRes);
	}
 
	/** Sets the value at ind to val. */
	void set(int ind, long val) { set(ind, val, 1, 0, len - 1); }
 
	/** @return the minimum element in the range [start, end] */
	long rangeSum(int start, int end) { return rangeSum(start, end, 1, 0, len - 1); }
 
	public SumSegmentTree(int len) {
		this.len = len;
		segtree = new long[len * 4];
	}
 
	public SumSegmentTree(long[] arr) {
		this.len = arr.length;
		segtree = new long[len * 4];
		build(arr, 1, 0, len - 1);
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int arrLen = io.nextInt();
		int queryNum = io.nextInt();
 
		long[] arr = new long[arrLen];
		for (int i = 0; i < arrLen; i++) { arr[i] = io.nextInt(); }
		SumSegmentTree segtree = new SumSegmentTree(arr);
 
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int arg1 = io.nextInt();
			int arg2 = io.nextInt();
			if (type == 1) {
				segtree.set(arg1 - 1, arg2);
			} else {
				io.println(segtree.rangeSum(arg1 - 1, arg2 - 1));
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


from typing import List, Optional
 
 
class SumSegmentTree:
	def __init__(self, arr: Optional[List[int]] = None, length: Optional[int] = None):
		self.DEFAULT = 0
		if arr is None:
			self.n = length
			self.segtree = [self.DEFAULT] * (self.n * 4)
		else:
			self.n = len(arr)
			self.segtree = [self.DEFAULT] * (self.n * 4)
			self._build(arr, 1, 0, self.n - 1)
 
	def _combine(self, a: int, b: int) -> int:
		return a + b
 
	def _build(self, arr: List[int], at: int, at_left: int, at_right: int) -> None:
		if at_left == at_right:
			self.segtree[at] = arr[at_left]
			return
		mid = (at_left + at_right) // 2
		self._build(arr, at * 2, at_left, mid)
		self._build(arr, at * 2 + 1, mid + 1, at_right)
		self.segtree[at] = self._combine(self.segtree[at * 2], self.segtree[at * 2 + 1])
 
	def _set(self, ind: int, val: int, at: int, at_left: int, at_right: int) -> None:
		if at_left == at_right:
			self.segtree[at] = val
			return
		mid = (at_left + at_right) // 2
		if ind <= mid:
			self._set(ind, val, at * 2, at_left, mid)
		else:
			self._set(ind, val, at * 2 + 1, mid + 1, at_right)
		self.segtree[at] = self._combine(self.segtree[at * 2], self.segtree[at * 2 + 1])
 
	def set(self, ind: int, val: int) -> None:
		if self.n == 0:
			return
		self._set(ind, val, 1, 0, self.n - 1)
 
	def _range_sum(
		self, start: int, end: int, at: int, at_left: int, at_right: int
	) -> int:
		if at_right < start or end < at_left:
			return self.DEFAULT
		if start <= at_left and at_right <= end:
			return self.segtree[at]
		mid = (at_left + at_right) // 2
		left_res = self._range_sum(start, end, at * 2, at_left, mid)
		right_res = self._range_sum(start, end, at * 2 + 1, mid + 1, at_right)
		return self._combine(left_res, right_res)
 
	def range_sum(self, start: int, end: int) -> int:
		if self.n == 0:
			return self.DEFAULT
		return self._range_sum(start, end, 1, 0, self.n - 1)
 
 
arr_len, query_num = map(int, input().split())
arr = list(map(int, input().split()))
segtree = SumSegmentTree(arr=arr)
 
out = []
for _ in range(query_num):
	t, a, b = map(int, input().split())
	if t == 1:
		segtree.set(a - 1, b)
	else:
		out.append(str(segtree.range_sum(a - 1, b - 1)))
 
print("\n".join(out))

Implementación iterativa

Complejidad temporal: $\mathcal{O}((N + Q) \log N)$

C++JavaPython


#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{Segment Tree}
template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;
 
	vector<T> segtree;
	int len;
 
  public:
	SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
		}
	}
 
	T range_sum(int start, int end) {
		T sum = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { sum += segtree[start++]; }
			if (end % 2 == 1) { sum += segtree[--end]; }
		}
		return sum;
	}
};
// EndCodeSnip
 
int main() {
	int arr_len;
	int query_num;
	std::cin >> arr_len >> query_num;
 
	SumSegmentTree<long long> segtree(arr_len);
	for (int i = 0; i < arr_len; i++) {
		int n;
		std::cin >> n;
		segtree.set(i, n);
	}
 
	for (int q = 0; q < query_num; q++) {
		int type, arg1, arg2;
		std::cin >> type >> arg1 >> arg2;
		if (type == 1) {
			segtree.set(arg1 - 1, arg2);
		} else if (type == 2) {
			cout << segtree.range_sum(arg1 - 1, arg2) << '\n';
		}
	}
}


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];
		Arrays.fill(segtree, 0);
	}
 
	public void set(int ind, int val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind >> 1] = segtree[ind] + segtree[ind ^ 1];
		}
	}
 
	public long rangeSum(int start, int end) {
		long total = 0;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { total += segtree[start++]; }
			if (end % 2 == 1) { total += segtree[--end]; }
		}
		return total;
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int arrLen = io.nextInt();
		int queryNum = io.nextInt();
 
		SumSegmentTree segtree = new SumSegmentTree(arrLen);
		for (int i = 0; i < arrLen; i++) { segtree.set(i, io.nextInt()); }
 
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int arg1 = io.nextInt();
			int arg2 = io.nextInt();
			if (type == 1) {
				segtree.set(arg1 - 1, arg2);
			} else {
				io.println(segtree.rangeSum(arg1 - 1, arg2));
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Comparado con la implementación anterior, lo único que hay que cambiar es la forma de agregar valores (de min() a ’+’), y cambiar el valor inicial a 0.


# BeginCodeSnip{Segment Tree}
class SumSegmentTree:
	def __init__(self, len_: int):
		self.len = len_
		self.tree = [0] * (2 * len_)
 
	def set(self, ind: int, val: int) -> None:
		ind += self.len
		self.tree[ind] = val
 
		while ind > 1:
			self.tree[ind // 2] = self.tree[ind] + self.tree[ind ^ 1]
			ind //= 2
 
	def range_sum(self, start: int, end: int) -> int:
		start += self.len
		end += self.len
		total = 0
		while start < end:
			if start % 2 == 1:
				total += self.tree[start]
				start += 1
			if end % 2 == 1:
				end -= 1
				total += self.tree[end]
 
			start //= 2
			end //= 2
		return total
 
 
# EndCodeSnip
 
 
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)
 
for _ in range(query_num):
	type_, arg1, arg2 = map(int, input().split())
	if type_ == 1:
		segtree.set(arg1 - 1, arg2)
	elif type_ == 2:
		print(segtree.range_sum(arg1 - 1, arg2))

Árbol de Fenwick

La implementación es más corta que la del árbol de segmentos, pero a primera vista puede resultar más confusa.

Recursos

Recursos
Fuente	Recurso	Notas
CSA	Fenwick Trees	interactivo
CPH	9.2, 9.4 - Binary Indexed Tree	similar a lo de arriba
cp-algo	Fenwick Tree	también similar a lo de arriba
TC	Binary Indexed Trees

Dynamic Range Sum Queries

Implementación

C++JavaPython

Recursos
Fuente	Recurso	Notas
CF	mouse_wireless - Multi-dimensional BITs with Templates
KACTL	FenwickTree


#include <cassert>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
/**
 * Short for "binary indexed tree",
 * this data structure supports point update and range sum
 * queries like a segment tree.
 */
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	/** Sets the value at index ind to val. */
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	/** Adds val to the element at index ind. */
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	/** @return The sum of all values in [0, ind]. */
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
 
int main() {
	int arr_len;
	int query_num;
	std::cin >> arr_len >> query_num;
 
	BIT<long long> bit(arr_len);
	for (int i = 0; i < arr_len; i++) {
		int n;
		std::cin >> n;
		bit.set(i, n);
	}
 
	for (int q = 0; q < query_num; q++) {
		int type, arg1, arg2;
		std::cin >> type >> arg1 >> arg2;
		if (type == 1) {
			bit.set(arg1 - 1, arg2);
		} else if (type == 2) {
			cout << bit.pref_sum(arg2 - 1) - bit.pref_sum(arg1 - 2) << '\n';
		}
	}
}


import java.io.*;
import java.util.*;
 
/**
 * Short for "binary indexed tree",
 * this data structure supports point update and range sum
 * queries like a segment tree.
 */
public class BIT {
	private final long[] bit;
	private final long[] arr;
	private final int len;
 
	public BIT(int len) {
		bit = new long[len + 1];
		arr = new long[len];
		this.len = len;
	}
 
	/** Sets the value of index ind at the actual array to vall. */
	public void set(int ind, long val) { add(ind, val - arr[ind]); }
 
	/** Adds val to the element at index ind. */
	public void add(int ind, long val) {
		arr[ind] += val;
		ind++;
		for (; ind <= len; ind += ind & -ind) { bit[ind] += val; }
	}
 
	/** @return The sum of all values in [0, ind]. */
	public long prefSum(int ind) {
		ind++;
		long sum = 0;
		for (; ind > 0; ind -= ind & -ind) { sum += bit[ind]; }
		return sum;
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int arrLen = io.nextInt();
		int queryNum = io.nextInt();
 
		BIT bit = new BIT(arrLen);
		for (int i = 0; i < arrLen; i++) { bit.set(i, io.nextInt()); }
 
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int arg1 = io.nextInt();
			int arg2 = io.nextInt();
			if (type == 1) {
				bit.set(arg1 - 1, arg2);
			} else if (type == 2) {
				io.println(bit.prefSum(arg2 - 1) - bit.prefSum((arg1 - 1) - 1));
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


class BIT:
	"""
	Short for "binary indexed tree",
	this data structure supports point update and range sum
	queries like a segment tree.
	"""
 
	def __init__(self, len_: int) -> None:
		self.bit = [0] * (len_ + 1)
		self.arr = [0] * len_
		self.len = len_
 
	def set(self, ind: int, val: int):
		"""Sets the value at ind to val"""
		self.add(ind, val - self.arr[ind])
 
	def add(self, ind: int, val: int):
		"""Adds val to the element at index ind."""
		self.arr[ind] += val
		ind += 1
		while ind <= self.len:
			self.bit[ind] += val
			ind += ind & -ind
 
	def pref_sum(self, ind: int):
		""":return: The sum of all values in [0, ind]."""
		ind += 1
		sum_ = 0
		while ind > 0:
			sum_ += self.bit[ind]
			ind -= ind & -ind
		return sum_
 
 
arr_len, query_num = map(int, input().split())
arr = list(map(int, input().split()))
 
bit = BIT(arr_len)
for i, v in enumerate(arr):
	bit.add(i, v)
 
for _ in range(query_num):
	q_type, arg1, arg2 = map(int, input().split())
	if q_type == 1:
		bit.set(arg1 - 1, arg2)
	elif q_type == 2:
		print(bit.pref_sum(arg2 - 1) - bit.pref_sum(arg1 - 2))

Hallar el $k$ -ésimo elemento

Supongamos que queremos una estructura de datos que soporte todas las operaciones de un set de C++ además de las siguientes:

order_of_key(x): cuenta la cantidad de elementos del conjunto que son estrictamente menores que x.
find_by_order(k): similar a find, devuelve el iterador correspondiente al $k$ -ésimo elemento más chico del conjunto (indexado desde 0).

Order Statistic Tree

Por suerte, esa estructura de datos ya existe de forma nativa en C++. Sin embargo, solo está soportada en GCC, así que quienes usen Clang no pueden contar con ella.

Recursos
Fuente	Recurso	Notas
CF	adamant - Policy Based Data Structures
CPH	4.5 - Policy Based Data Structures	panorama breve con find_by_order y order_of_key
KACTL	OrderStatisticTree	código

Con un BIT

Sin embargo, si todas las actualizaciones están en el rango $[1,N]$ , podemos hacer lo mismo con un BIT.

Recursos
Fuente	Recurso	Notas
CF	adamant - About Ordered Set	log N

Con un Árbol de Segmentos

Se cubre en Platino.

Conteo de inversiones

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	Inversion Counting	Fácil	PURS	en el módulo

Implementación

C++JavaPython

Usando un indexed set, podemos resolver esto en apenas unas líneas.


#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() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		Tree<int> tree;
 
		int arr_len;
		cin >> arr_len;
		long long inv_num = 0;
		for (int i = 0; i < arr_len; i++) {
			int x;
			cin >> x;
			/*
			 * Calculate the # of elements in the tree
			 * that are greater than x.
			 * (.order_of_key(x) gives the # of elements less than x)
			 */
			inv_num += i - tree.order_of_key(x);
			tree.insert(x);
		}
 
		cout << inv_num << '\n';
	}
}

Observar que si no fuera cierto que todos los elementos del arreglo de entrada son distintos, este código sería incorrecto porque Tree<int> eliminaría duplicados. En ese caso usaríamos un indexed set de pares (Tree<pair<int,int>>), donde el primer elemento de cada par denotaría el valor y el segundo la posición del valor en el arreglo.


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++) {
			BIT bit = new BIT(MAX_ELEM + 1);
 
			int arrLen = io.nextInt();
			long invNum = 0;
			for (int i = 0; i < arrLen; i++) {
				int x = io.nextInt();
				bit.add(x, 1);
				invNum += bit.prefSum(MAX_ELEM) - bit.prefSum(x);
			}
 
			io.println(invNum);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}
 
// BeginCodeSnip{BIT Code}
class BIT {
	private final long[] bit;
	private final int len;
 
	public BIT(int len) {
		bit = new long[len + 1];
		this.len = len;
	}
 
	public void add(int ind, long val) {
		ind++;
		for (; ind <= len; ind += ind & -ind) { bit[ind] += val; }
	}
 
	public long prefSum(int ind) {
		ind++;
		long sum = 0;
		for (; ind > 0; ind -= ind & -ind) { sum += bit[ind]; }
		return sum;
	}
}
// EndCodeSnip


# BeginCodeSnip{BIT}
class BIT:
	def __init__(self, len_: int) -> None:
		self.bit = [0] * (len_ + 1)
		self.arr = [0] * len_
		self.len = len_
 
	def add(self, ind: int, val: int):
		self.arr[ind] += val
		ind += 1
		while ind <= self.len:
			self.bit[ind] += val
			ind += ind & -ind
 
	def pref_sum(self, ind: int):
		ind += 1
		sum_ = 0
		while ind > 0:
			sum_ += self.bit[ind]
			ind -= ind & -ind
		return sum_
 
 
# EndCodeSnip
 
MAX_ELEM = 10**7
 
test_num = int(input())
for _ in range(test_num):
	bit = BIT(MAX_ELEM + 1)
 
	input()
	arr_len = int(input())
	inv_num = 0
	for _ in range(arr_len):
		x = int(input())
		bit.add(x, 1)
		inv_num += bit.pref_sum(MAX_ELEM) - bit.pref_sum(x)
 
	print(inv_num)

Problemas

General

Fuente	Nombre	Dificultad	Tags	Solución
CSES	★ Range Update Queries	Fácil	PURS	Solución
Kattis	Mega Inversions	Fácil	PURS, Inversions	Solución
CSES	List Removals	Fácil	PURS	Solución
CSES	Salary Queries	Fácil	PURS, Coordinate Compress	Solución
CF	Irrigation	Fácil	PURS, Binary Search, Offline	Solución
CSES	Increasing Subsequence II	Fácil	PURS, Coordinate Compress	Solución
CSES	★ Distinct Values Queries	Normal	PURS, Offline	Solución
CSES	Pyramid Array	Difícil	PURS, Inversions	Solución

USACO

Fuente	Nombre	Dificultad	Tags	Solución
Gold	★ Haircut	Fácil	PURS, Inversions	Solución
Gold	Balanced Photo	Fácil	PURS, Inversions	Solución
Gold	Circle Cross	Fácil	PURS, Inversions	Solución
Gold	Sleepy Cow Sorting	Fácil	PURS	Solución
Platinum	Mincross	Fácil	PURS, Inversions	Solución
Old Gold	Cow Hopscotch	Difícil	PURS	—

Actualización puntual y suma de rango

Árbol de Segmentos

Recursos

Dynamic Range Minimum Queries

Implementación recursiva

Implementación iterativa

Dynamic Range Sum Queries

Implementación recursiva

Implementación iterativa

Árbol de Fenwick

Recursos

Dynamic Range Sum Queries

Implementación

Hallar el kkk-ésimo elemento

Order Statistic Tree

Con un BIT

Con un Árbol de Segmentos

Conteo de inversiones

Implementación

Problemas

General

USACO

Hallar el $k$ -ésimo elemento