snippets_competetive-programming/segmenttree.sublime-snippet at master · hackybacky/snippets_competetive-programming · 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

<snippet>
    <content><![CDATA[
int t[27][4*N];
int a[N];

void build( int v, int tl, int tr) {
    if (tl == tr) {
        t[a[tl]][v] ++;
    } else {
        int tm = (tl + tr) / 2;
        build( v*2, tl, tm);
        build( v*2+1, tm+1, tr);
        forr(i,26){
            t[i][v]=t[i][2*v]+t[i][2*v+1];
        }
    }
}


void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        int d=a[tl];
        a[tl]=new_val;
        t[new_val][v]++;
        t[d][v]--;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        forr(i,26){
            t[i][v]=t[i][2*v]+t[i][2*v+1];
        }

    }
}

int query(int v,int y, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr) {
        return t[y][v];
    }
    int tm = (tl + tr) / 2;
    return query(v*2,y, tl, tm, l, min(r, tm))
           + query(v*2+1,y, tm+1, tr, max(l, tm+1), r);
}


]]></content>
  <tabTrigger>segmenttree</tabTrigger>
</snippet>