// estisさんのやつがベース
struct<T> SegmentTree {
e: u64,
size: usize,
tree: Vec<u64>,
cmpfn: T,
}
impl<T> SegmentTree<T> where T: Fn(u64, u64) -> u64 {
/// 値の初期化
pub fn new(n: usize, e: u64, arr: &[u64], cmpfn: fn(u64, u64) -> u64) -> SegmentTree {
let mut size: usize = 1;
while size < n {
size <<= 1;
}
let mut tree: Vec<u64> = Vec::<u64>::with_capacity(2*size);
for _ in 0..2*size {
tree.push(e);
}
for (i, val) in arr.iter().enumerate() {
tree[size + i] = *val;
}
for i in (1..size).map(|x| size-x) {
tree[i] = cmpfn(tree[2*i], tree[2*i+1]);
}
SegmentTree{
e,
size,
tree,
cmpfn,
}
}
/// indexの値をnumで更新する.
pub fn update_number(&mut self, mut index: usize, num: u64) {
self.tree[index + self.size] = num;
index = (index + self.size) / 2;
while index > 0 {
self.tree[index] = (self.cmpfn)(self.tree[2*index], self.tree[2*index+1]);
index >>= 1;
}
}
/// [l, r)での範囲の答えを得る.
pub fn get(&self, l: usize, r:usize) -> u64 {
// println!("{}, {}, {}", self.size, l, r);
self.rec(0,self.size,l,r)
}
fn rec(&self, min: usize, max: usize, l: usize, r:usize) -> u64 {
let mid = (min + max)/2;
if l == min && r == max {
return self.tree[self.size/(r-l) + l/(r-l)];
}
if l < mid && mid < r{
(self.cmpfn)(self.rec(min, mid, l, mid) , self.rec(mid, max, mid, r))
}else if mid <= l {
self.rec(mid, max, l, r)
}else if r <= mid {
self.rec(min, mid, l, r)
}else{
0
}
}
fn debug(&self){
println!("{:?}", self.tree);
}
}