Point Update Range Sum

C++

Copy
#include <algorithm>
#include <cassert>
#include <iostream>
#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
import sys


class SegmentTree:
	"""A data structure that can answer point update & range minimum queries."""

	def __init__(self, arr: list[int], n: int) -> None:
		self.arr = arr
		self.n = n
		self.tree = [0] * (2 * n)

C++

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

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

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

template <class T> class SumSegmentTree {
  private:

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 (sum) to 0.

Copy
import sys


class SegmentTree:
	def __init__(self, arr: list[int], n: int) -> None:
		self.arr = arr
		self.n = n
		self.tree = [0] * (2 * n)

		for ii in range(n):

C++

Solution 1

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
import sys


class BIT:
	"""
	Short for "binary indexed tree",
	this data structure supports point update and range sum
	queries like a segment tree.
	"""