真调不出来了/oh

#include <bits/stdc++.h>

using namespace std;

#define BUF_SIZE 1048576
#define getchar() gc()
#define putchar(x) pc(x)
static char buf[BUF_SIZE], *p1 = buf, *p2 = buf, obuf[BUF_SIZE], *p3 = obuf;
inline void fls() { fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf; }
inline void ffls() { fls(), fflush(stdout); }
inline char gc() {
  return p1 == p2 &&
                 (p2 = (p1 = buf) + fread(buf, 1, BUF_SIZE, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline void pc(char x) {
  if (p3 - obuf >= BUF_SIZE) fls();
  *p3++ = x;
}

#define ll int
#define isi(n) (n >= '0' && n <= '9')
inline ll read() {
  ll x = 0;
  char ch = getchar(), sign = '+';
  while (!isi(ch)) sign = ch, ch = getchar();
  do x = x * 10 + (ch ^ 48), ch = getchar();
  while (isi(ch));
  return sign == '-' ? -x : x;
}
inline void write(ll x, char l = '\n') {
  if (x) {
    char n[20];
    int cnt = 0;
    if (x < 0) putchar('-'), x = -x;
    do n[cnt++] = x % 10 ^ 48, x /= 10;
    while (x);
    do putchar(n[--cnt]);
    while (cnt);
  } else
    putchar('0');
  putchar(l);
}

const int SIZE = 500000;
struct node {
  int l, r, sum, ls, rs, ms;
} t[SIZE << 2];
void merge(node& p, node& l, node& r) {
  p.sum = l.sum + r.sum, p.ls = max(l.ls, l.sum + r.ls),
  p.rs = max(r.rs, r.sum + l.rs), p.ms = max(max(l.ms, r.ms), l.rs + r.ls);
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].sum = t[p].ls = t[p].rs = t[p].ms = read();
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  merge(t[p], t[p << 1], t[p << 1 | 1]);
}
void change(int p, int x, int v) {
  if (t[p].l == t[p].r) {
    t[p].sum = t[p].ls = t[p].rs = t[p].ms = v;
    return;
  }
  int mid = (t[p].l + t[p].r) >> 1;
  if (x <= mid)
    change(p << 1, x, v);
  else
    change(p << 1 | 1, x, v);
  merge(t[p], t[p << 1], t[p << 1 | 1]);
}
node query(int p, int l, int r) {
  if (t[p].l >= l && t[p].r <= r) return t[p];
  int mid = (t[p].l + t[p].r) >> 1;
  if (t[p].r <= mid)
    return query(p << 1, l, r);
  else if (t[p].l > mid)
    return query(p << 1 | 1, l, r);
  else {
    node a = query(p << 1, l, r), b = query(p << 1 | 1, l, r), w;
    merge(w, a, b);
    return w;
  }
}

int main() {
  int n = read(), m = read(), k, a, b;
  build(1, 1, n);
  while (m--) {
    k = read(), a = read(), b = read();
    if (k & 1)
      write(query(1, min(a, b), max(a, b)).ms);
    else
      change(1, a, b);
  }
  fls();
  return 0;
}