HackPack/SegmentTree.java at master · JacobSteinebronn/HackPack · 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
class segmentTree {
	public static void main (String[] args) {
	    int n;
	    node seg = new node(1, n);

	}
	static class node{
	    long li, ri, m;
	    long sum, min, lazy = 0;
	    node l = null, r = null;
	    node(long liIn, long riIn){
	        li = liIn;
	        ri = riIn;
	        m = (li + ri) / 2;
	        if(li != ri){
	            l = new node(li, m);
	            r = new node(m + 1, ri);
	        }
	    }
	    void add(int s, int e, int v){
	        if(s <= li && ri <= e){
	            sum += (ri - li + 1) * v;
	            min += v;
	            lazy += v;
	            return;
	        }

	        push();
	        if(s <= m) l.add(s, e, v);
	        if(e > m) r.add(s, e, v);
	        sum = l.sum + r.sum;
	        min = Math.min(l.min, r.min);
	    }
	    long getSum(int s, int e){
	        if(s <= li && ri <= e) return sum;

	        push();
	        long out = 0;
	        if(s <= m) out += l.getSum(s, e);
	        if(e > m) out += r.getSum(s, e);
	        return out;
	    }
	    long getMin(int s, int e){
	        if(s <= li && ri <= e) return min;

	        push();
	        long out = Long.MAX_VALUE;
	        if(s <= m) out = Math.min(out, l.getMin(s, e));
	        if(e > m) out = Math.min(out, r.getMin(s, e));
	        return out;
	    }
	    void push(){
	        l.lazy += lazy;
	        l.sum += (l.ri - l.li + 1) * lazy;
	        l.min += lazy;

	        r.lazy += lazy;
	        r.sum += (r.ri - r.li + 1) * lazy;
	        r.min += lazy;

	        lazy = 0;
	    }
	}
}