Algorithms/SegmentTree.cpp at master · Tejas988/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
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;
int N;
int tree[4N + 1];
int lazy[1000] = {0}; //initialise lazy to 0


//min max sum multiply gcd xor or and as they are associative a+(b+c)=(a+b)+c
void lazyupdate(int s, int e, int indx, int val, int l, int r)
{
	// l and r are the range which we need to update
	//val is the value which needs to be added

	// if lazy exists on current indx then resolve it and pass down to its children if its non leaf

	if (lazy[indx] != 0)
	{
		tree[indx] += lazy[indx];
		if (s != e)
		{
			//non leaf
			lazy[2 * indx] = lazy[indx];
			lazy[2 * indx + 1] = lazy[indx];
		}
		lazy[indx] = 0;
	}
	//no overlap
	if (s > r or e < l)
		return;


	if (s >= l and e <= r)
	{
		//complete overlap
		tree[indx] += val;
		if (s != e)
		{
			lazy[2 * indx] += val;
			lazy[2 * indx + 1] += val;
		}
		return;
	}

	//recursive case - partial overlap
	int mid = (s + e) / 2;
	upadteRange(s, mid, 2 * indx, val, l, r);
	upadteRange(mid + 1, e, 2 * indx + 1, val, l, r);

	// update tree while returning up
	tree[indx] = min(tree[2 * indx], tree[2 * indx + 1]);
	return;
}


//fun for returning value in range
int queryLazy(int s, int e, int L, int R, int indx)
{
	if (lazy[indx] != 0)
	{
		tree[indx] += lazy[indx];
		if (s != e)
		{
			//non leaf
			lazy[2 * indx] = lazy[indx];
			lazy[2 * indx + 1] = lazy[indx];
		}
		lazy[indx] = 0;
	}
	//no overlap
	if (s > r or e < l)
		return INT_MAX;
	if (s >= l and e <= r)
	{
		//complete overlap
		return tree[indx];
	}
	//partial overlap
	int mid = (s + e) / 2;
	upadteRange(s, mid, 2 * indx, val, l, r);
	upadteRange(mid + 1, e, 2 * indx + 1, val, l, r);
	// update tree while returning up
	return min(tree[2 * indx], tree[2 * indx + 1]);

}


void buildTree(int s, int e, int indx, int a[])
{
	if (s == e)
	{
		tree[indx] = a[s];
		return;
	}
	int mid = (s + e) / 2;
	buildTree(s, mid, 2 * indx, a);
	buildTree(mid + 1, e, 2 * indx + 1, a);
	tree[indx] = min(tree[2 * indx], tree[2 * indx + 1]);
	return;
}

int query(int s, int e, int L, int R, int indx)
{
	//complete overlap

	// L and R is query range and s and e are array ranges of a node

	//indx is node
	if (L <= s and R >= e)
		return tree[indx];
	if (L > e and R < s)
		return INT_MAX;
	int mid = (s + e) / 2;
	int left = query(s, mid, L, R, 2 * indx);
	int right = query(mid + 1, e, L, R, 2 * indx + 1);
	return min(left, right);
}

void update(int s, int e, int val, int indx, int i)
{

	// s and e is array  range of a node
	if (i > e or i < s)
	{
		return;
	}
	if (ss == se)
	{
		tree[indx] = val;
		return;
	}
	int mid = (s + e) / 2;
	update(s, mid, val, 2 * indx, i);
	update(mid + 1, e, val, 2 * indx + 1, i);
	tree[indx] = min(tree[2 * indx], tree[2 * indx + 1]);
	return;
}
void upadteRange(int s, int e, int l, int r, int val, int indx)
{
	// s and e is array  range of a node
	if (l > e || r < s)
	{
		return;
	}
	if (s == e)
	{
		tree[indx]  = val;
		return;
	}
	int mid = (s + e) / 2;
	upadteRange(s, mid, l, r, val, 2 * indx);
	upadteRange(mid + 1, e, l, r, val, 2 * indx + 1);
	tree[indx] = min(tree[2 * indx], tree[2 * indx + 1]);
	return;
}
int main()
{
	int a[] = {1, 2, 3, 4, -13, 34, 2, -3};
	N = sizeof(a) / sizeof(int);

	return 0;
}