simpleSegmentTree.cpp

#include <stdio.h>

#define INF 1000000000

struct node
{
  node *left, *right;
  int l, r;
  int vl;
} typedef node;

node* root;

// Builds segment tree with range ['l', 'r']
void build(node* cur, int l, int r)
{
  cur->l = l;
  cur->r = r;
  cur->vl = 0;

  if (l == r)
    return;

  cur->left = new node();
  cur->right = new node();

  int m = (cur->l + cur->r) / 2;

  build(cur->left, cur->l, m);
  build(cur->right, m + 1, cur->r);

  cur->vl = min(cur->left->vl, cur->right->vl);
}

// Updates value in position 'p' to 'vl'
void update(node* cur, int p, int vl)
{
  if (cur->l == p && cur->r == p)
  {
    cur->vl = vl;
    return;
  }

  if (cur->l > p || cur->r < p)
    return;

  update(cur->left, p, vl);
  update(cur->right, p, vl);

  cur->vl = min(cur->left->vl, cur->right->vl);
}

// Queries minimum in interval ['l', 'r']
int query(node* cur, int l, int r)
{
  if (cur == NULL)
    return INF;

  if (cur->r < l || cur->l > r)
    return INF;

  if (cur->l >= l && cur->r <= r)
    return cur->vl;

  return min(query(cur->left, l, r), query(cur->right, l, r));
}

int main()
{
  int n, q;
  scanf("%d %d", &n, &q);

  root = new node();
  build(root, 0, n - 1);

  for (int i = 0; i < q; i++)
  {
    int tp, a, b;
    scanf("%d %d %d", &tp, &a, &b);

    if (tp == 1)
      printf("%d\n", query(root, a, b));
    else
      update(root, a, b);
  }

  return 0;
}