cpp-algorithms/segment_tree.txt at master · hamidsultanzadeh/cpp-algorithms · 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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
 * File:   segment_tree.cpp
 * Author: hamidsultanzadeh
 *
 * Created on November 30, 2019, 12:03
 */

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define DEBUG(x) cout<<"DEBUG - "<<x<<"\n";
#define DEBUGs(code,x) cout<<"DEBUG - "<<code<<" : "<<x<<"\n";
#define FOR(i,s,f) for(int i = s ; i < f ; i++)
#define MID(v1,v2) (v1 + (v2 - v1)/2)

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

//
//                  -- [0:4] (15) --
//                /                   \
//           [0:2] (6)              (9) [3:4]
//             /    \                /       \
//      [0:1] (3) (3) [2:2]     [3:3] (4) (5) [4:4]
//           / \
//  [0:0] (1)   (2) [1:1]

// QEYDLER
// 0. SEGMENT POINTER GLOBALDA - UYGUN OPTIMAL
// 1. start  == finish olduqa , yeni [1:1], [2:2] , [0:0] massivin
// geride qalan elementi menimsedilir
// 2. left node 2*currentIndex + 1 , right node 2*currentIndex + 2
// 3. segment tree height = ceil log2 n ( node uzunlugu 2 nin derece ile )
// 4. segment tree maxsize = pow 2 height - 1 ( node - larin sayi )
// 5. dynamic array da sizeof funksiyasi duzgun ishlemir deyene, size tapmaq
// uchun vector dan istifade etmek olar.

void updateValueUtil(int *st, int start, int finish, int index, int diff, int current){

    if(index < start || index > finish) return ;

    st[current] += diff;

    if(start!=finish){

        int mid = MID(start, finish);
        updateValueUtil(st,start,mid,index,diff,2*current+1);
        updateValueUtil(st,mid+1,finish,index,diff,2*current+2);

    }

}

void updateValue(int arr[],int *st,int size, int index, int newValue){

    if(index < 0 || index > size - 1){
        cout<<"Invalid input";
        return;
    }

    int diff = newValue - arr[index];

    DEBUGs("different",diff);

    arr[index] = newValue;

    updateValueUtil(st, 0, size - 1, index, diff, 0);

}

int getSumUtil(int *st,int begin, int end, int start, int finish,int current){

    if(start <= begin && finish >= end) return st[current];

    if(end < start || begin > finish) return 0;

    int mid = MID(begin, end);

    return getSumUtil(st, begin, mid,start, finish, 2*current+1)+
            getSumUtil(st, mid+1,end, start, finish, 2*current+2);

}

int getSum(int *st,int size, int start, int finish){

    if(start < 0 || finish > size - 1 || start > finish){
        cout<<"Invalid input";
        return -1;
    }

    return getSumUtil(st, 0, size - 1,start, finish, 0);

}

int constructSTUtil(int arr[], int start, int finish, int *st, int current){

    // eger arr - da bir element qalibsa, onu hemin node a atiriq
    if(start == finish){
        st[current] = arr[start];
        return arr[start];
    }

    int mid = MID(start,finish);

    // soldaki 2*i + 1 , sagdaki 2*i + 2
    st[current] = constructSTUtil(arr,start,mid,st,current*2+1) +
            constructSTUtil(arr,mid + 1,finish,st,current*2+2);

    return st[current];
}

int *constructST(int arr[],int size){

    // uzunlugu , asagi dogru
    int length = (int)(ceil(log2(size)));

    DEBUGs("length",length);

    // yaddash
    int maxSize = 2 * (int)pow(2, length) - 1;

    DEBUGs("max size",maxSize);

    // util
    int *st = new int[maxSize];
    constructSTUtil(arr, 0, size - 1, st, 0);

    return st;
}

int main(int argc, char** argv) {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int arr[5] = {1,2,3,4,5};
    int size = sizeof (arr) / sizeof (int);

    // verilen arr - dan segment tree yaradiriq
    int *st = constructST(arr, size);

    int i;
    FOR(i, 0,2*size-1) DEBUG(*(st+i));

    cout<<getSum(st,size,0,4)<<"\n";

    updateValue(arr,st,size,3,10);

    FOR(i, 0,2*size-1) DEBUG(*(st+i));

    cout<<getSum(st,size,0,4);


    return 0;
}