Codes_of_Inititated/Segment_Tree.cpp at main · Initiated0/Codes_of_Inititated · 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
91
92
#include <bits/stdc++.h>

using namespace std;

int num[8+3];
int sum[8*4+3];


int SegmentTreeQuery(int AT, int L, int R, int l, int r)
{
    if(r < L || l > R) return 0; // either the range is l...r...L....R or L...R...l...r
    if(l <= L && r >= R) return sum[AT]; // l...L...R...r

    // L...l...r...R

    int mid = (L + R) / 2;

    int x = SegmentTreeQuery(AT*2, L, mid, l, r);
    int y = SegmentTreeQuery(AT* 2 + 1, mid+ 1, R, l, r);

    return x+y;

}

void SegmentTreeUpdate(int AT, int L, int R, int pos, int u)
{
    if(L == R)
    {
        sum[AT] += u;
        return;
    }

    int mid = (L+R) / 2;

    if (mid >= pos) SegmentTreeUpdate(AT * 2, L, mid, pos, u);
    else SegmentTreeUpdate(AT * 2 + 1, mid + 1, R, pos, u);

    sum[AT] = sum[AT*2] + sum[AT*2 + 1];

    return;

}


void SegmentTreeBuild(int AT, int L, int R)
{
    sum[AT] = 0;

    if(L == R)
    {
        sum[AT] = num[L];
        return;
    }

    int mid = (L+R)/2;

    SegmentTreeBuild(AT*2, L, mid);
    SegmentTreeBuild(AT*2+1, mid+1, R);

    sum[AT] = sum[AT*2] + sum[AT*2+1];

    return;
}

int main()
{
    freopen("ST.txt", "r", stdin);
    for(int i = 1; i<= 8; i++)
        scanf("%d", &num[i]);

    SegmentTreeBuild(1, 1, 8); // first one is at, second one is leftmost in the range,
                               // and third is rightmost in the range
    for(int i = 1; i<= 8; i++)
        cout<<num[i]<<" ";
    cout<<endl;

    for(int i = 1; i<= 20; i++)
        cout<<sum[i]<<" ";
    cout<<endl;

    SegmentTreeUpdate(1, 1, 8, 3, 10);


    for(int i = 1; i<= 20; i++)
        cout<<sum[i]<<" ";
    cout<<endl;

    cout<<SegmentTreeQuery(1, 1, 8, 5, 8)<<endl;


    return 0;
}