Point Update Range Sum

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 minimum queries. */

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 problem, all we need to change are DEFAULT and how we combine the elements.

Copy
#include <iostream>
#include <vector>

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

 Code Snippet: Segment Tree (Click to expand)

int main() {

Java

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

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 problem, 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

Using a binary indexed tree, we can count the number of inversions.

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

public class Main {
	public static void main(String[] args) {
		final int MAX_ELEM = (int)1e7;
		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())