#ifdef LOCAL
#include <debug.hpp>
#else
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,tune=native")
#define debug(...)
#endif 

#include <bits/stdc++.h>

using namespace std;

/*
struct Lazy {
  int val = 0;
  // Combine lazy with lazy
  Lazy& operator+=(const Lazy& oth) {
    val += oth.val;
    return *this;
  }
};
struct Node {
  int val = 0;
  // Combine node with node
  Node& operator+=(const Node& oth) {
    val += oth.val;
    return *this;
  }
  // Combine node with lazy
  Node& operator+=(const Lazy& oth) {
    val += oth.val;
    return *this;
  }
};
*/

template<typename Node, typename Lazy>
struct GenericSegTree {
  int n;
  vector<Node> T;
  vector<Lazy> L;

  GenericSegTree(int n) : n(n), T(2 * n), L(2 * n) {}
  
  void push(int x, int z) {
    Lazy& l = L[x];
    T[x] += l;
    if (z > x) L[x + 1] += l, L[z] += l;
    l = {};
  }
  void pull(int x, int z) { 
    T[x] = T[x + 1]; 
    T[x] += T[z]; 
  }
  template<typename Func>
  void go(int x, int b, int e, int l, int r, Func&& f) {
    int m = (b + e) / 2, z = x + 2 * (m - b);
    push(x, z);
    l = max(l, b); r = min(r, e);
    if (l >= r) return;
    if (b == l && e == r && f(x, b, e)) return;
    go(x + 1, b, m, l, r, f);
    go(z, m, e, l, r, f);
    pull(x, z);
  }

  template<typename Func>
  void Go(int l, int r, Func&& f) {
    go(1, 0, n, l, r, f);
  }
};

struct Node {
  int val;
  void operator+=(Node oth) {
    val = max(val, oth.val);
  }
  void operator+=(int oth) {
    val += oth;
  }
};
struct SegTree : GenericSegTree<Node, int> { 
  SegTree(vector<Node>& v) : GenericSegTree(v.size()) {
    Go(0, n, [&](int x, int b, int e) {
      if (b + 1 == e) {
        T[x] = v[b];
        return true;
      }
      return false;
    });
  }

  Node Sum(int l, int r) {
    T[0] = {};
    Go(l, r, [&](int x, int b, int e) {
      T[0] += T[x];
      return true;
    });
    return T[0];
  }

  void Set(int i, Node v) {
    Go(i, i + 1, [&](int x, int b, int e) {
      T[x] = v;
      return true;
    });
  }
};

int main() {
  ifstream cin("arbint.in");
  ofstream cout("arbint.out");

  int n, m; cin >> n >> m;
  vector<Node> v(n);
  for (int i = 0; i < n; ++i) 
    cin >> v[i].val;
  SegTree st(v);

  for (int i = 0; i < m; ++i) {
    int t; cin >> t;
    if (t == 0) {
      int a, b; cin >> a >> b;
      cout << st.Sum(a - 1, b).val << '\n';
    } else {
      int a; Node b; cin >> a >> b.val;
      st.Set(a - 1, b);
    }
  }

  return 0;
}