给定一个长度为 $n$ 的序列 $a$，每次单点修改或者查询区间最大子段和。

考虑动态 dp。首先，我们定义 $dp_{i, 0 / 1}$ 为前 $i$ 个数，是否选 $a_i$ 为当前和最大的子段的末尾，有转移：

$$f_{i, 1} = \max(f_{i - 1, 1}, 0) + a_i, f_{i, 0} = \max(f_{i - 1, 0}, f_{i, 1})$$

考虑搞成矩阵的形式，并且使用 $(\max, +)$ 运算，那么容易得到关系：

$$\left[ \begin{array}{cc} -\infty & 0 & 0 \\ -\infty & -\infty & -\infty \\ -\infty & -\infty & -\infty \\ \end{array} \right] \times \prod_{i = l} ^ r\left[ \begin{array}{cc} 0 & -\infty & -\infty \\ a_i & a_i & -\infty \\ a_i & a_i & 0 \\ \end{array} \right] = \left[ \begin{array}{cc} dp_{n, 0} & dp_{n, 1} & 0 \\ -\infty & -\infty & -\infty \\ -\infty & -\infty & -\infty \end{array} \right]$$

线段树维护即可。

#include <bits/stdc++.h>

constexpr int N = 1e5 + 6;

struct Mat {
  int mat[3][3];
  Mat() {
    memset(mat, -0x3F, sizeof mat);
  }
  int* operator[](int idx) {
    return mat[idx];
  }
  friend Mat operator*(Mat a, Mat b) {
    Mat c;
    for (int k = 0; k < 3; ++k) {
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            c[i][j] = std::max(c[i][j], a[i][k] + b[k][j]);
        }
      }
    }
    return c;
  }
};

void debug(Mat mat) {
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      std::cerr << mat[i][j] << " ";
    }
    std::cerr << "\n";
  }
}

void solve() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
  }
  auto get = [&](int x) -> Mat {
    Mat mat;
    mat[0][0] = mat[2][2] = 0;
    mat[1][0] = mat[1][1] = mat[2][0] = mat[2][1] = x;
    return mat;
  };
  std::vector<Mat> tree(n * 4 + 1);
#define ls(u) (u * 2)
#define rs(u) (u * 2 + 1)
  auto pull = [&](int x) -> void {
    tree[x] = tree[ls(x)] * tree[rs(x)];
  };
  auto upd = [&](auto &&self, int u, int l, int r, int idx, Mat x) -> void {
    if (l == r) {
      tree[u] = x;
      return;
    }
    int mid = l + r >> 1;
    (idx <= mid ? self(self, ls(u), l, mid, idx, x) : self(self, rs(u), mid + 1, r, idx, x));
    pull(u);
  };
  auto qry = [&](auto &&self, int u, int l, int r, int ql, int qr) -> Mat {
    if (ql <= l && r <= qr) return tree[u];
    int mid = l + r >> 1;
    if (ql <= mid && qr > mid) return self(self, ls(u), l, mid, ql, qr) * self(self, rs(u), mid + 1, r, ql, qr); 
    if (ql <= mid) return self(self, ls(u), l, mid, ql, qr);
    else return self(self, rs(u), mid + 1, r, ql, qr);
  };
  for (int i = 1; i <= n; ++i) {
    upd(upd, 1, 1, n, i, get(a[i]));
  }
  Mat fr;
  fr[0][1] = fr[0][2] = 0;
  while (q--) {
    int op, l, r;
    std::cin >> op >> l >> r;
    if (op == 2) upd(upd, 1, 1, n, l, get(r));
    else {
        if (l > r) std::swap(l, r);
        Mat res = fr * qry(qry, 1, 1, n, l, r);
        std::cout << res[0][0] << "\n";
    }
  }  
#undef ls
#undef rs
}

int32_t main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0), std::cout.tie(0);

  int t;
  // std::cin >> t;
  t = 1;

  while (t--) {
    solve();
  }

  return 0;
}