algorithm/segment_tree(templte).cpp at main · ihbadhon/algorithm · 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
template<class T>
struct Segtree
{
#define segtre int m=(x+y)>>1,lu=2*u,ru=2*u+1
    struct data
    {
        T v;
        data()
        {
            this->v=0;
        }
        data(T v)
        {
            this->v=v;
        }
    };
    vector<T>ara;
    vector<data>t;
    int n;

    Segtree(){}
    Segtree(int n)
    {
        this->n=n;
        t=vector<data>(4*n);
    }

    void Init(vector<T>vec)
    {
        this->ara=vec;
        Init(1,0,n-1);  /// check 0 or 1 indexed
    }
    void Update(int l,int r,T val)
    {
        Update(1,0,n-1,l,r,val);   /// check 0 or 1 indexed
    }
    data Query(int l,int r)
    {
        return Query(1,0,n-1,l,r);    /// check 0 or 1 indexed
    }
    data Combine(data a,data b)
    {
        data temp;
        temp.v=a.v+b.v;
        return temp;
    }
    void Init(int u,int x,int y)
    {
        if(x==y)
        {
            t[u].v=ara[x];
            return;
        }
        segtre;
        Init(lu,x,m);
        Init(ru,m+1,y);
        t[u]=Combine(t[lu],t[ru]);
    }
    void Update(int u,int x,int y,int b,int e,T val)
    {
        if(x>e||y<b)
            return;
        if(x>=b&&y<=e)
        {
            t[u].v+=val;
            return;
        }
        segtre;
        Update(lu,x,m,b,e,val);
        Update(ru,m+1,y,b,e,val);
        t[u]=Combine(t[lu],t[ru]);
    }
    data Query(int u,int x,int y,int b,int e)
    {
        if(x>e||y<b)
            return data();    ///check this
        if(x>=b&&y<=e)
            return t[u];
        segtre;
        data res1=Query(lu,x,m,b,e);
        data res2=Query(ru,m+1,y,b,e);
        return Combine(res1,res2);
    }
};