algo-codes/segment-tree.cpp at master · iabhishek15/algo-codes · 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
#include <bits/stdc++.h>
using namespace std;


int const nax = 2e5 + 11;
int n;
long long v[nax];
long long seg[nax * 4];

//for sum

void build_sum(int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = v[start];
    return ;
  }
  int mid = (start + end) / 2;
  build_sum(start, mid, index * 2);
  build_sum(mid + 1,end, index * 2 + 1);

  seg[index] = seg[index * 2] + seg[index * 2 + 1];
}
long long query_sum(int x, int y, int start = 1, int end = n, int index = 1) {
  if ((start >= x) &&  (end <= y)) {
    return seg[index];
  }
  if ((y < start) || (x > end)) {
    return 0;
  }
  int mid = (start + end) / 2;
  return query_sum(x, y, start, mid, index * 2) + query_sum(x, y, mid + 1, end, index * 2 + 1);
}

void update_sum(int given_index, long long value, int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = value;
    return ;
  }
  int mid = (start + end) / 2;
  if (given_index <= mid) {
    update_sum(given_index, value, start, mid, index * 2);
  }else {
    update_sum(given_index, value, mid + 1, end, index * 2 + 1);
  }
  seg[index] = seg[2 * index] + seg[2 * index + 1];
}


//for min

void build_min(int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = v[start];
    return ;
  }
  int mid = (start + end) / 2;
  build_min(start, mid, index * 2);
  build_min(mid + 1,end, index * 2 + 1);
  seg[index] = min(seg[index * 2], seg[index * 2 + 1]);
}

long long query_min(int x, int y, int start = 1, int end = n, int index = 1) {
  if ((start >= x) &&  (end <= y)) {
    return seg[index];
  }
  if ((y < start) || (x > end)) {
    return 1e18 + 17;
  }
  int mid = (start + end) / 2;
  return min(query_min(x, y, start, mid, index * 2), query_min(x, y, mid + 1, end, index * 2 + 1));
}

void update_min(int given_index, long long value, int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = value;
    return ;
  }
  int mid = (start + end) / 2;
  if (given_index <= mid) {
    update_min(given_index, value, start, mid, index * 2);
  }else {
    update_min(given_index, value, mid + 1, end, index * 2 + 1);
  }
  seg[index] = min(seg[index * 2], seg[index * 2 + 1]);
}


//for max
void build_max(int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = v[start];
    return ;
  }
  int mid = (start + end) / 2;
  build_max(start, mid, index * 2);
  build_max(mid + 1,end, index * 2 + 1);

  seg[index] = max(seg[index * 2], seg[index * 2 + 1]);
}

long long query_max(int x, int y, int start = 1, int end = n, int index = 1) {
  if ((start >= x) &&  (end <= y)) {
    return seg[index];
  }
  if ((y < start) || (x > end)) {
    return -1e18 - 7;
  }
  int mid = (start + end) / 2;
  return max(query_max(x, y, start, mid, index * 2), query_max(x, y, mid + 1, end, index * 2 + 1));
}

void update_max(int given_index, long long value, int start = 1, int end = n, int index = 1) {
  if (start == end) {
    seg[index] = value;
    return ;
  }
  int mid = (start + end) / 2;
  if (given_index <= mid) {
    update_max(given_index, value, start, mid, index * 2);
  }else {
    update_max(given_index, value, mid + 1, end, index * 2 + 1);
  }
  seg[index] = max(seg[index * 2], seg[index * 2 + 1]);
}