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
use std::mem;
use std::ops::Add;
use std::ops::Sub;
pub struct TreePrefix < V > where V: Add< Output = V > + Sub< Output = V > + Default + Clone {
_buf: Vec< V >,
}
impl < V > TreePrefix < V > where V: Add< Output = V > + Sub< Output = V > + Default + Clone {
pub fn init( num: usize ) -> TreePrefix< V > {
TreePrefix {
_buf: vec![ Default::default(); num + 1]
}
}
pub fn add( & mut self, index: usize, val: V ){
assert!( index < self._buf.len() );
let mut i = index;
while i < self._buf.len() {
let v = self._buf[i].clone();
self._buf[i] = v + val.clone();
i += self.lsb(i+1);
}
}
pub fn set( & mut self, index: usize, val: V ){
assert!( index < self._buf.len() );
let v = self.get( index );
self.add( index, val - v );
}
pub fn get( & self, index: usize ) -> V {
assert!( index < self._buf.len() );
self.get_interval( index, index + 1 )
}
pub fn get_interval( & self, index: usize, index_end: usize ) -> V {
assert!( index < self._buf.len() );
assert!( index_end < self._buf.len() );
let mut s = Default::default();
let mut i = index_end;
let mut j = index;
if j > i {
mem::swap( & mut i, & mut j );
}
while i > j {
s = s + self._buf[i-1].clone();
i = i - self.lsb(i);
}
while j > i {
s = s - self._buf[j-1].clone();
j = j - self.lsb(j);
}
s
}
pub fn get_interval_start( & self, index: usize ) -> V {
let mut i = index;
let mut s = Default::default();
while i > 0 {
s = s + self._buf[i-1].clone();
i = i - self.lsb(i);
}
s
}
pub fn get_len( & mut self ) -> usize {
self._buf.len() - 1
}
fn lsb( & self, v: usize ) -> usize {
let a = !v + 1;
let b = a & v;
b
}
}