我叫豆包，是个能陪你搞定不少事的全能小伙伴呀～ 平时能陪你聊日常、解小疑问，也能帮你写文案、查信息、整理琐事，不管是想找乐子还是有实际需求，都能喊我！ @

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;  // 数组最大长度
int n, m;
int w[N];  // 存储原始数组

// 线段树节点结构
struct Node {
    int l, r;          // 节点覆盖的区间 [l, r]
    int sum;           // 区间内所有元素的总和
    int lmax;          // 从左端点开始的最大连续子段和（必须包含左端点）
    int rmax;          // 到右端点结束的最大连续子段和（必须包含右端点）
    int tmax;          // 区间内的最大连续子段和（任意位置）
} tr[N * 4];  // 线段树数组，大小为4*N以确保足够

// 用左右孩子节点的信息更新父节点信息
void pushup(Node& u, Node& l, Node& r) {
    u.sum = l.sum + r.sum;  // 父节点总和 = 左孩子总和 + 右孩子总和
    // 父节点左最大：要么左孩子的左最大，要么左孩子总和+右孩子左最大（跨左右）
    u.lmax = max(l.lmax, l.sum + r.lmax);
    // 父节点右最大：要么右孩子的右最大，要么右孩子总和+左孩子右最大（跨左右）
    u.rmax = max(r.rmax, r.sum + l.rmax);
    // 父节点最大连续和：左孩子最大、右孩子最大、或左孩子右最大+右孩子左最大（跨左右）
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}

// 重载pushup，通过节点编号更新（u为父节点编号）
void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);  // u<<1是左孩子，u<<1|1是右孩子
}

// 构建线段树
// u：当前节点编号，l、r：当前节点覆盖的区间
void build(int u, int l, int r) {
    if (l == r) {  // 叶子节点（单个元素）
        tr[u] = {l, r, w[r], w[r], w[r], w[r]};  // 四个值均为该元素值
    } else {
        tr[u].l = l;
        tr[u].r = r;
        int mid = l + r >> 1;  // 计算中点
        build(u << 1, l, mid);    // 递归构建左子树
        build(u << 1 | 1, mid + 1, r);  // 递归构建右子树
        pushup(u);  // 用左右子树更新当前节点
    }
}

// 单点修改：将位置x的值改为v
// u：当前节点编号，x：目标位置，v：新值
void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {  // 找到目标叶子节点
        tr[u] = {x, x, v, v, v, v};  // 更新叶子节点信息
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) {  // x在左子树范围内
            modify(u << 1, x, v);
        } else {  // x在右子树范围内
            modify(u << 1 | 1, x, v);
        }
        pushup(u);  // 修改后更新当前节点信息
    }
}

// 区间查询：查询[l, r]范围内的最大连续子段和
// u：当前节点编号，l、r：查询区间
Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {  // 当前节点区间完全在查询范围内
        return tr[u];  // 直接返回当前节点信息
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) {  // 查询区间仅在左子树
            return query(u << 1, l, r);
        } else if (l > mid) {  // 查询区间仅在右子树
            return query(u << 1 | 1, l, r);
        } else {  // 查询区间横跨左右子树
            auto left = query(u << 1, l, r);   // 查询左子树部分
            auto right = query(u << 1 | 1, l, r);  // 查询右子树部分
            Node res;  // 合并结果
            pushup(res, left, right);  // 用左右结果生成合并后的节点信息
            return res;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);  // 读入数组长度和操作次数
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);  // 读入数组元素
    }
    build(1, 1, n);  // 从根节点（编号1）开始构建线段树，覆盖区间[1, n]

    while (m--) {  // 处理m次操作
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1) {  // 查询操作
            if (x > y) swap(x, y);  // 确保x <= y
            // 查询[x, y]并输出最大连续子段和
            printf("%d\n", query(1, x, y).tmax);
        } else {  // 修改操作：将位置x的值改为y
            modify(1, x, y);
        }
    }
    return 0;
}