C++

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

Java

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

C++

Copy
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <class T> class MinSegmentTree {

Java

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

Python

Copy
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

C++

Compared to the previous implementation, all we need to change are DEFAULT and how we combine the elements.

Copy
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: Segment Tree (Click to expand)

Java

Compared to the previous implementation, all we need to change is the way we combine the elements, the default value, and the data type we use for the segment tree (from int to long).

Copy
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) {

C++

Copy
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: Segment Tree (Click to expand)

int main() {

Java

Copy
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];

Python

Compared to the previous implementation, all we need to change is the way we aggregate values (from min() to '+'), and change the initial value to 0.

Copy
 Code Snippet: Segment Tree (Click to expand)


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)

C++

Copy
#include <cassert>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/**
 * Short for "binary indexed tree",

Java

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

/**
 * Short for "binary indexed tree",
 * this data structure supports point update and range sum
 * queries like a segement tree.
 */
public class BIT {
	private final long[] bit;

Python

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

C++

Using an indexed set, we can solve this in just a few lines.

Copy
#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() {

Note that if it were not the case that all elements of the input array were distinct, then this code would be incorrect since Tree<int> would remove duplicates. Instead, we would use an indexed set of pairs (Tree<pair<int,int>>), where the first element of each pair would denote the value while the second would denote the position of the value in the array.

Java

Copy
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++) {

Python

Copy
 Code Snippet: BIT (Click to expand)

MAX_ELEM = 10**7

test_num = int(input())
for _ in range(test_num):
	bit = BIT(MAX_ELEM + 1)

	input()
	arr_len = int(input())