segment tree

1// C++ program to show segment tree operations like construction, query 
2// and update 
3#include <bits/stdc++.h> 
4using namespace std; 
5
6// A utility function to get the middle index from corner indexes. 
7int getMid(int s, int e) { return s + (e -s)/2; } 
8
9/* A recursive function to get the sum of values in the given range 
10	of the array. The following are parameters for this function. 
11
12	st --> Pointer to segment tree 
13	si --> Index of current node in the segment tree. Initially 
14			0 is passed as root is always at index 0 
15	ss & se --> Starting and ending indexes of the segment represented 
16				by current node, i.e., st[si] 
17	qs & qe --> Starting and ending indexes of query range */
18int getSumUtil(int *st, int ss, int se, int qs, int qe, int si) 
19{ 
20	// If segment of this node is a part of given range, then return 
21	// the sum of the segment 
22	if (qs <= ss && qe >= se) 
23		return st[si]; 
24
25	// If segment of this node is outside the given range 
26	if (se < qs || ss > qe) 
27		return 0; 
28
29	// If a part of this segment overlaps with the given range 
30	int mid = getMid(ss, se); 
31	return getSumUtil(st, ss, mid, qs, qe, 2*si+1) + 
32		getSumUtil(st, mid+1, se, qs, qe, 2*si+2); 
33} 
34
35/* A recursive function to update the nodes which have the given 
36index in their range. The following are parameters 
37	st, si, ss and se are same as getSumUtil() 
38	i --> index of the element to be updated. This index is 
39			in the input array. 
40diff --> Value to be added to all nodes which have i in range */
41void updateValueUtil(int *st, int ss, int se, int i, int diff, int si) 
42{ 
43	// Base Case: If the input index lies outside the range of 
44	// this segment 
45	if (i < ss || i > se) 
46		return; 
47
48	// If the input index is in range of this node, then update 
49	// the value of the node and its children 
50	st[si] = st[si] + diff; 
51	if (se != ss) 
52	{ 
53		int mid = getMid(ss, se); 
54		updateValueUtil(st, ss, mid, i, diff, 2*si + 1); 
55		updateValueUtil(st, mid+1, se, i, diff, 2*si + 2); 
56	} 
57} 
58
59// The function to update a value in input array and segment tree. 
60// It uses updateValueUtil() to update the value in segment tree 
61void updateValue(int arr[], int *st, int n, int i, int new_val) 
62{ 
63	// Check for erroneous input index 
64	if (i < 0 || i > n-1) 
65	{ 
66		cout<<"Invalid Input"; 
67		return; 
68	} 
69
70	// Get the difference between new value and old value 
71	int diff = new_val - arr[i]; 
72
73	// Update the value in array 
74	arr[i] = new_val; 
75
76	// Update the values of nodes in segment tree 
77	updateValueUtil(st, 0, n-1, i, diff, 0); 
78} 
79
80// Return sum of elements in range from index qs (quey start) 
81// to qe (query end). It mainly uses getSumUtil() 
82int getSum(int *st, int n, int qs, int qe) 
83{ 
84	// Check for erroneous input values 
85	if (qs < 0 || qe > n-1 || qs > qe) 
86	{ 
87		cout<<"Invalid Input"; 
88		return -1; 
89	} 
90
91	return getSumUtil(st, 0, n-1, qs, qe, 0); 
92} 
93
94// A recursive function that constructs Segment Tree for array[ss..se]. 
95// si is index of current node in segment tree st 
96int constructSTUtil(int arr[], int ss, int se, int *st, int si) 
97{ 
98	// If there is one element in array, store it in current node of 
99	// segment tree and return 
100	if (ss == se) 
101	{ 
102		st[si] = arr[ss]; 
103		return arr[ss]; 
104	} 
105
106	// If there are more than one elements, then recur for left and 
107	// right subtrees and store the sum of values in this node 
108	int mid = getMid(ss, se); 
109	st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) + 
110			constructSTUtil(arr, mid+1, se, st, si*2+2); 
111	return st[si]; 
112} 
113
114/* Function to construct segment tree from given array. This function 
115allocates memory for segment tree and calls constructSTUtil() to 
116fill the allocated memory */
117int *constructST(int arr[], int n) 
118{ 
119	// Allocate memory for the segment tree 
120
121	//Height of segment tree 
122	int x = (int)(ceil(log2(n))); 
123
124	//Maximum size of segment tree 
125	int max_size = 2*(int)pow(2, x) - 1; 
126
127	// Allocate memory 
128	int *st = new int[max_size]; 
129
130	// Fill the allocated memory st 
131	constructSTUtil(arr, 0, n-1, st, 0); 
132
133	// Return the constructed segment tree 
134	return st; 
135} 
136
137// Driver program to test above functions 
138int main() 
139{ 
140	int arr[] = {1, 3, 5, 7, 9, 11}; 
141	int n = sizeof(arr)/sizeof(arr[0]); 
142
143	// Build segment tree from given array 
144	int *st = constructST(arr, n); 
145
146	// Print sum of values in array from index 1 to 3 
147	cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl; 
148
149	// Update: set arr[1] = 10 and update corresponding 
150	// segment tree nodes 
151	updateValue(arr, st, n, 1, 10); 
152
153	// Find sum after the value is updated 
154	cout<<"Updated sum of values in given range = "
155			<<getSum(st, n, 1, 3)<<endl; 
156	return 0; 
157} 
158//This code is contributed by rathbhupendra 
159

1const int N = 1e5;  // limit for array size
2int n;  // array size
3int t[2 * N];
4
5void build() {  // build the tree
6  	for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
7}
8
9void modify(int p, int value) {  // set value at position p
10  	for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
11}
12
13int query(int l, int r) {  // sum on interval [l, r)
14    int res = 0;
15    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
16        if (l&1) res += t[l++];
17        if (r&1) res += t[--r];
18    }
19    return res;
20}
21
22int main() {
23	std::cin>>n;
24    for (int i = 0; i < n; ++i) std::cin>>t[n+i];
25    build();
26    modify(0, 1);
27    std::cout<<query(3, 11)<<'\n';
28    return 0;
29}

1// General Segment Tree struct
2// Original source: https://codeforces.com/blog/entry/18051
3
4template<class T> struct SegTree {
5
6    int size;
7    T defVal;
8    vector<T> tree;
9    T (*op)(T, T);
10    
11    SegTree (int size, T defVal, T (*op)(T, T))
12        : size(size), defVal(defVal), tree(vector<T>(2*size)), op(op) {}
13    SegTree (vector<T> v, T defVal, T (*op)(T, T))
14        : SegTree(v.size()/2, defVal, op) {
15        for (int i = 0; i<size; ++i) {
16            tree[i+size] = v[i];
17        }
18        build();
19    }
20
21    void build() {
22
23        for (int i = size-1; i>0; --i) {
24            tree[i] = op(tree[i<<1], tree[i<<1|1]);
25        }
26
27    }
28    T query (int l, int r) {
29
30        l += size, r += size+1;
31        T res;
32        for (res = defVal; l<r; l >>= 1, r >>= 1) {
33            if (l&1) res = op(res, tree[l++]);
34            if (r&1) res = op(res, tree[--r]);
35        }
36        return res;
37
38    }
39    void update (int i, T val) {
40
41        i += size;
42        for (tree[i] = val; i>1; i >>= 1) {
43            tree[i>>1] = op(tree[i], tree[i^1]);
44        }
45
46    }
47
48};

1//Given size of array,array elements and no. of queries along with the range l,r find the minimum value in the range
2#include<bits/stdc++.h>
3using namespace std;
4int build_segment_tree(int arr[],int start,int end,int *st,int index)
5{
6    if(start==end)
7    {
8        st[index]=arr[start];
9        return arr[start];
10    }
11    int mid=(start+end)/2;
12    st[index]=min(build_segment_tree(arr,start,mid,st,2*index+1),build_segment_tree(arr,mid+1,end,st,2*index+2));
13    return st[index];
14}
15int* construct_seg_tree(int arr[],int n)
16{
17    int height=(int)(ceil(log2(n)));
18    int max_length=2*(int)pow(2,height)-1;
19    int* segtree=new int[max_length];
20    build_segment_tree(arr,0,n-1,segtree,0);
21    return segtree;
22}
23int range_query_min(int* st,int start,int end, int l,int r,int index)
24{
25    if(l>=start&&r<=end)//total overlap
26    {
27        return st[index];
28    }
29    else if(l>end||r<start)
30    {
31        return INT_MAX;
32    }
33    else
34    {
35        int mid=(start+end)/2;
36        return min(range_query_min(st,start,mid,l,r,2*index+1),range_query_min(st,mid+1,end,l,r,2*index+2));
37    }
38}
39int range_query(int *st,int start,int end,int l,int r,int index)
40{
41    if(l<0||r>end-1||l>r)
42    {
43        cout<<"Enter a valid range"<<endl;
44        return -1;
45    }
46    return range_query_min(st,0,end-1,l,r,0);
47}
48int main()
49{
50    int n;
51    cout<<"enter the size of array"<<endl;
52    cin>>n;
53    int arr[n];
54    cout<<"Enter the elements of the array:"<<endl;
55    for(int i=0;i<n;i++)
56    {
57        cin>>arr[i];
58    }
59    int *segment=construct_seg_tree(arr,n);
60    cout<<"enter the query range"<<endl;
61    int l,r;
62    cin>>l>>r;
63    cout<<range_query(segment,0,n,l,r,0);
64    return 0;
65}
66

1void build(int node, int start, int end)
2{
3    if(start == end)
4    {
5        // Leaf node will have a single element
6        tree[node] = A[start];
7    }
8    else
9    {
10        int mid = (start + end) / 2;
11        // Recurse on the left child
12        build(2*node, start, mid);
13        // Recurse on the right child
14        build(2*node+1, mid+1, end);
15        // Internal node will have the sum of both of its children
16        tree[node] = tree[2*node] + tree[2*node+1];
17    }
18}