Pizzeria Queries

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define endl '\n'

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};

class SegTreeIterative{
private:
  typedef int Node;
  Node neutral = INF;
  vector<Node> st;
  int n;
  inline Node join(Node a, Node b){
    return min(a, b);
  }
public:
  SegTreeIterative(int sz){
    for (n = 1; n < sz; n <<= 1);
    st.assign(n << 1, neutral);
  }
  //0-indexed
  void update(int i, Node x){
    st[i += n] = x;
    for (i >>= 1; i; i >>= 1)
      st[i] = join(st[i << 1], st[(i << 1) + 1]);
  }
  //0-indexed [l, r]
  Node query(int l, int r){
    Node ansL = neutral, ansR = neutral;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1){
      if (l & 1)
        ansL = join(ansL, st[l++]);
      if (r & 1)
        ansR = join(st[--r], ansR);
    }
    return join(ansL, ansR);
  }
};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);

  int n, q;
  cin >> n >> q;
  SegTreeIterative left(n), right(n);
  for(int i=0; i<n; i++){
    int x;
    cin >> x;
    left.update(i, x - i);
    right.update(i, x + i);
  }
  for(int i=1; i<=q; i++){
    int op;
    cin >> op;
    if(op == 1){
      int k, x;
      cin >> k >> x; k--;
      left.update(k, x - k);
      right.update(k, x + k);
    }else{
      int k;
      cin >> k; k--;
      int a = left.query(0, k) + k; // x - i + k = x + | k - i |
      int b = right.query(k, n-1) - k; // x + i - k = x + | i - k |
      cout << min(a, b) << endl;
    }
  }
  return 0;
}