Segment Tree

Samar Anand

·

Follow

2 min read

·

Jun 22, 2021

--

Listen

Share

A Segment Tree is a data structure used mainly to find in-range queries. Since range queries can be solved is using prefix array but if there is an update, we can get help from the segment tree.

Like in with the segment tree we can get sum of ar[l…r] easily or also we can update the value of any pos b/w 0…n-1 with the new value.

/*
** @samaranand **
*/#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi = vector<int>;
const int N = 4 * (1e5 + 2);// suppose if we have n = 1e5
// so we will need 4*n size of array to make a segment treeint arr[N];// we can implement segment tree on many type of functions
// but here i have assumed for the sum queryvoid build(vi &v, int u, int tl, int tr) {
 if (tl == tr) arr[u] = v[tl];
 else {
  int tm = (tl + tr) / 2;
  build(v, 2 * u, tl, tm);
  build(v, 2 * u + 1, tm + 1, tr);
  arr[u] = arr[2 * u] + arr[2 * u + 1];
 }
}// pos is 0-inedxed position where new value is updated
void update(int u, int tl, int tr, int pos, int value) {
 if (tl == tr) {
  arr[u] = value;
 } else {
  int tm = (tl + tr) / 2;
  if (pos <= tm) update(2 * u, tl, tm, pos, value);
  else update(2 * u + 1, tm + 1, tr, pos, value);
  arr[u] = arr[2 * u] + arr[2 * u + 1];
 }
}// l & r is the 0-indexed range from where we want result sum
int resQuery(int u, int tl, int tr, int l, int r) {
 if (l > r) return 0;
 if (tl == l and tr == r) return arr[u];
 int tm = (tl + tr) / 2;
 int a = resQuery(2 * u, tl, tm, l, min(tm, r));
 int b = resQuery(2 * u + 1, tm + 1, tr, max(l, tm + 1), r);
 return a + b;
}int main() {
 // total size og given array
 int n; cin >> n;
 vi v(n);
 // taking input of array
 for (int i = 0; i < n; i++) cin >> v[i];// calling build fun to build the segment tree
 build(v, 1, 0, n - 1);// total number of query
 int q; cin >> q;for (int i = 0; i < q; i++) {
  int t;
  cin >> t;
  // here i assumed 2 type of query
  // 1st is update so t == 1
  // 2nd is range sum query so t == 2
  // Iassumed 0-indexing for query
  if (t == 1) {
   // for update query, we need pos & value
   int pos, val;
   cin >> pos >> val;
   update(1, 0, n - 1, pos, val);
  } else {
   // for range query, we need l & r
   int l, r;
   cin >> l >> r;
   cout << resQuery(1, 0, n - 1, l, r) << endl;
  }}return 0;
}