CompetitivePrograming/SegmentTree_Monoidtemplate.cpp at master · taiseiKMC/CompetitivePrograming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
usage:
SegmentTree<T> tree(array, PLUS) で(array, +, 1)のセグツリーができる
update: 更新
fold:   畳み込み
*/

template<class Monoid>
struct SegmentTree
{
	using M = Monoid;
	using T = typename M::type;

	const int SIZE;
	int tree_size, leaf_number;
	vector<T> node;

	SegmentTree(const vector<T> &ary);

	const int child_l(const int k) const
	{
		return k*2+1;
	}
	const int child_r(const int k) const
	{
		return k*2+2;
	}
	const int parent(const int k) const
	{
		return (k-1)/2;
	}
	const int least_square(const int k) const
	{
		if(k==0) return 0;
		int tmp=k-1;
		for(int i=1; 64>i; i<<=1)
			tmp |= (tmp >> i);
		return tmp+1;
	}

	const T init(const int k);
	const void update(const int k, const T x);
	const T fold(const int a, const int b, const int k, const int l, const int r) const;
	const T fold(const int a,const int b) const
	{
		return fold(a, b, 0, 0, leaf_number);
	}

	const void print() const
	{
		for(int i=0;i<tree_size;i++)
			cout<<node[i]<<" \n"[i==tree_size-1];
	}
};

template<class M>
SegmentTree<M>::SegmentTree(const vector<T> &ary):SIZE(ary.size())
{
	tree_size=SIZE;
	leaf_number=least_square(tree_size);
	tree_size=leaf_number*2;
	node=vector<T>(tree_size);
	tree_size--;

	for(int i=0;i<leaf_number;i++)
		if(i<SIZE)
			node[i+leaf_number-1]=ary[i];
		else
			node[i+leaf_number-1]=M::id();

	init(0);
}


template<class M>
const typename SegmentTree<M>::T SegmentTree<M>::init(const int k)
{
	if(k>=leaf_number-1) return node[k];
	return node[k]=M::op(init(child_l(k)),init(child_r(k)));
}

template<class M>
const void SegmentTree<M>::update(const int k, const T x)
{
	int tmp = k+leaf_number-1;
	node[tmp]=x;
	while(tmp > 0)
	{
		tmp=parent(tmp);
		node[tmp]=M::op(node[child_l(tmp)], node[child_r(tmp)]);
	}
}

template<class M>
const typename SegmentTree<M>::T SegmentTree<M>::fold(const int a, const int b, const int k, const int l, const int r) const
{
	if(r <= a || b <= l)
		return M::id();  //[a,b)と[l,r)が交わらない
	if(a <= l && r <= b)
		return node[k];    //[a,b)が[l,r)を含む

	return M::op(fold(a,b,child_l(k),l,(l+r)/2), fold(a,b,child_r(k),(l+r)/2, r));
}

template <typename T>
struct MinMonoid
{
	using type = T;
	static constexpr T id() { return numeric_limits<T>::max(); }
	static T op(const T &a, const T &b) { return min(a, b); }
};

template <typename T>
struct MaxMonoid
{
	using type = T;
	static constexpr T id() { return numeric_limits<T>::min(); }
	static T op(const T &a, const T &b) { return max(a, b); }
};

template <typename T>
struct AddMonoid
{
	using type = T;
	static constexpr T id() { return 0; }
	static T op(const T &a, const T &b) { return a + b; }
};

template <typename T>
struct MultMonoid
{
	using type = T;
	static constexpr T id() { return 1; }
	static T op(const T &a, const T &b) { return a * b; }
};

template <typename T>
using RMQ = SegmentTree<MinMonoid<T>>;

template <typename T>
using RSM = SegmentTree<AddMonoid<T>>;