PracticasProgramacionCompetitiva/maxSegmentTree.cpp at main · AnahiSU/PracticasProgramacionCompetitiva · 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
/*
- Science is knowledge which we understand so well
  that we can teach it to a computer; and if we don’t
  fully understand something, it is an art to deal with it.
- El trabajo duro supera al talento cuando el talento no trabaja duro.
- Los desafios son los que hacen la vida interesante y superarlos es
  lo que hace a la vida significativa.
- Para sentirse vivo se necesita una meta en la que trabajar.
*/

typedef long long ll;
#define srt(a) sort((a).begin(),(a).end());
#define srtR(a) sort((a).rbegin(),(a).rend());

#include <bits/stdc++.h>
using namespace std;

// Max segment tree
struct segtree {
    int n;
    vector<ll> tree;

    void init(int nn) {
        tree.clear();
        n = nn;
        int size = 1;
        while (size < n) {
            size *= 2;
        }
        tree.resize(size * 2);
    }

    void update(int i, int sl, int sr, int pos, ll diff) {
        if (sl <= pos && pos <= sr) {
            if (sl == sr) {
                tree[i] += diff;
            } else {
                int mid = (sl + sr) / 2;
                update(i * 2 + 1, sl, mid, pos, diff);
                update(i * 2 + 2, mid + 1, sr, pos, diff);
                tree[i] = max(tree[i * 2 + 1], tree[i * 2 + 2]);
            }
        }
    }

    void update(int pos, ll diff) {
        update(0, 0, n - 1, pos, diff);
    }

    ll query(int i, int sl, int sr, int l, int r) {
        if (l <= sl && sr <= r) {
            return tree[i];
        } else if(sr < l || r < sl) {
            return INT64_MIN;
        } else {
            int mid = (sl + sr) / 2;
            auto a = query(i * 2 + 1, sl, mid, l, r);
            auto b = query(i * 2 + 2, mid + 1, sr, l, r);
            return max(a, b);
        }
    }

    ll query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
};

signed main (){
    ios::sync_with_stdio(false);cin.tie(0);

    return 0;
}

//                   :-==-.                     .:..
//                .+%@@@@@@#-                -*%@@@@#+.
//              .%@@@@@@@@@@%*=--:.....::--+#@@@@@@@@@@@=
//              +@@@@@@@%*-.                 .-*%@@@@@@@%
//              +@@@@@%=.                       .=%@@@@@@.
//              -@@@@*.                           .+@@@@%
//               +@@+    ..                         =@@%:
//                -*  :*%@@@*.             :+#%#+.   +#:
//                =. =@@@*=+@%            :%@##@@@+  .+
//                + -@@@@.  #@:  :-----   *@=  +@@@+  +
//               .+ #@@@@#+*@%.  *@@@@%.  +@#:-#@@@@: =.
//               .=  @@@@@@@@+    .=*:     :@@@@@@@@= -:
//                + :**%@%*:     .-=+--     :#@@%**+  +
//                +.---:.                     .----- .=
//                 :=                               +.
//                    :=-.                     .-=:
//                           .:-----------:.