'''
线段树应用，维护每个区间的区段总和，区段最大前缀和，区段最大后缀和，区段最大连续字段和
'''


import sys
class SegmentTreeLazy:
    class Node:
        def __init__(self, start, end):
            self.start = start      # 区段开始位置
            self.end = end          # 区段结束位置
            self.left = None        # 左节点
            self.right = None       # 右节点

            self.sum = 0                    # 区段总和
            self.max_prefix_sum = 0         # 区段最大前缀和
            self.max_suffix_sum = 0         # 区段最大后缀和
            self.max_sum = 0                # 区段中最大连续子段和


    # 更新单个数据
    def _update_single(self, root, idx, data):
        if root.start == root.end and root.start == idx:
            root.sum = data
            root.max_prefix_sum = root.sum
            root.max_suffix_sum = root.sum
            root.max_sum = root.sum

        else:
            mid = (root.start + root.end) // 2

            if idx <= mid:
                self._update_single(root.left, idx, data)
            else:
                self._update_single(root.right, idx, data)

            sum1, max_prefix_sum1, max_suffix_sum1, max_sum1 = root.left.sum, root.left.max_prefix_sum, root.left.max_suffix_sum, root.left.max_sum
            sum2, max_prefix_sum2, max_suffix_sum2, max_sum2 = root.right.sum, root.right.max_prefix_sum, root.right.max_suffix_sum, root.right.max_sum

            root.sum = sum1 + sum2
            root.max_prefix_sum = max(max_prefix_sum1, sum1 + max_prefix_sum2)
            root.max_suffix_sum = max(max_suffix_sum2, sum2 + max_suffix_sum1)
            root.max_sum = max(max_sum1, max_sum2, max_suffix_sum1 + max_prefix_sum2)

    # 获取区间数据
    def _get_data(self, idx, start, end):
        root = self.__nodes[idx]
        if root.start == start and root.end == end:
            return root.sum, root.max_prefix_sum, root.max_suffix_sum, root.max_sum

        else:
            mid = (root.start + root.end) // 2

            if end <= mid:
                return self._get_data(2*idx+1, start, end)
            elif start >= mid + 1:
                return self._get_data(2*idx+2, start, end)
            else:
                sum1, max_prefix_sum1, max_suffix_sum1, max_sum1 = self._get_data(2*idx+1, start, mid)
                sum2, max_prefix_sum2, max_suffix_sum2, max_sum2 = self._get_data(2*idx+2, mid+1, end)
                sum = sum1 + sum2
                max_prefix_sum = max(max_prefix_sum1, sum1 + max_prefix_sum2)
                max_suffix_sum = max(max_suffix_sum2, sum2 + max_suffix_sum1)
                max_sum = max(max_sum1, max_sum2, max_suffix_sum1 + max_prefix_sum2)
                return sum, max_prefix_sum, max_suffix_sum, max_sum

    def update_single(self, idx, data):
        self._update_single(self.root, idx, data)

    from functools import lru_cache
    @lru_cache(typed=False, maxsize=128000000)
    def get_data(self, start, end, time_stamp):
        return self._get_data(0, start, end)

    def __init__(self, n):
        self.__nodes = [self.Node(0, 0) for _ in range(4*n)]
        nodes = self.__nodes
        nodes[0].start, nodes[0].end = 0, n - 1
        self.root = self.__nodes[0]

        for i in range(4*n):
            if nodes[i].start == n-1 and nodes[i].end == n-1:
                break

            mid = (nodes[i].start + nodes[i].end) // 2
            nodes[i].left = nodes[2*i+1]
            nodes[i].left.start, nodes[i].left.end = nodes[i].start, mid

            nodes[i].right = nodes[2*i+2]
            nodes[i].right.start, nodes[i].right.end = mid+1, nodes[i].end

n, m = map(int, input().split())
s = sys.stdin.readline()
arr = list(map(int, s.split()))


tree = SegmentTreeLazy(n)
for i, val in enumerate(arr):
    tree.update_single(i, val)

ans = []
time_stamp = 0
for i in range(m):
    s = sys.stdin.readline()
    cmd, val1, val2 = map(int, s.split())
    if cmd == 1:
        if val1 > val2:
            val1, val2 = val2, val1
        ans.append(tree.get_data(val1-1, val2-1, time_stamp)[3])
    else:
        tree.update_single(val1-1, val2)
        time_stamp += 1

for val in ans:
    sys.stdout.write(str(val))
    sys.stdout.write('\n')
    sys.stdout.flush()

Python 版本会超时，C++ AC 版本如下

#include <stdio.h>
#include <algorithm>

using namespace std;


struct Node {
    int start;          // 区间开始位置
    int end;            // 区间结束位置
    int sum;            // 区间总和
    int max_prefix_sum; // 区间最大前缀和
    int max_suffix_sum; // 区间最大后缀和
    int max_sum;        // 区间最大连续区段和
} __global_nodes[500005 * 4];

struct Data {
    int sum;            // 区间总和
    int max_prefix_sum; // 区间最大前缀和
    int max_suffix_sum; // 区间最大后缀和
    int max_sum;        // 区间最大连续区段和
};

int arr[500005];

class SegmentTree {
private:
    Node *__nodes;      // 节点数组
    int __n;            // 区间为0到n-1

    // 更新单个位置的数值
    void __update_single(int node_idx, int pos, int val) {
        Node &node = __nodes[node_idx];

        if (node.start == node.end) {
            node.sum = node.max_prefix_sum = node.max_suffix_sum = node.max_sum = val;
            return;
        }

        int mid = (node.start + node.end) >> 1;
        if (pos <= mid) {
            __update_single(node_idx * 2 + 1, pos, val);
        } else {
            __update_single(node_idx * 2 + 2, pos, val);
        }

        int sum1 = __nodes[node_idx * 2 + 1].sum, max_prefix_sum1 = __nodes[node_idx * 2 + 1].max_prefix_sum;
        int max_suffix_sum1 = __nodes[node_idx * 2 + 1].max_suffix_sum, max_sum1 = __nodes[node_idx * 2 + 1].max_sum;
        int sum2 = __nodes[node_idx * 2 + 2].sum, max_prefix_sum2 = __nodes[node_idx * 2 + 2].max_prefix_sum;
        int max_suffix_sum2 = __nodes[node_idx * 2 + 2].max_suffix_sum, max_sum2 = __nodes[node_idx * 2 + 2].max_sum;

        node.sum = sum1 + sum2;
        node.max_prefix_sum = max(max_prefix_sum1, sum1 + max_prefix_sum2);
        node.max_suffix_sum = max(max_suffix_sum2, sum2 + max_suffix_sum1);
        node.max_sum = max( max_suffix_sum1 + max_prefix_sum2, max(max_sum1, max_sum2) );
    }

    // 获取区间统计信息
    Data __get_val(int node_idx, int start, int end) {

        Node &node = __nodes[node_idx];
        if (node.start == start && node.end == end) {
            return {node.sum, node.max_prefix_sum, node.max_suffix_sum, node.max_sum};
        }

        int mid = (node.start + node.end) >> 1;
        if (end <= mid) {
            return __get_val(node_idx * 2 + 1, start, end);
        } else if (start >= mid + 1) {
            return __get_val(node_idx * 2 + 2, start, end);
        } else {
            Data data1 = __get_val(node_idx * 2 + 1, start, mid);
            Data data2 = __get_val(node_idx * 2 + 2, mid + 1, end);

            int sum1 = data1.sum, max_prefix_sum1 = data1.max_prefix_sum;
            int max_suffix_sum1 = data1.max_suffix_sum, max_sum1 = data1.max_sum;
            int sum2 = data2.sum, max_prefix_sum2 = data2.max_prefix_sum;
            int max_suffix_sum2 = data2.max_suffix_sum, max_sum2 = data2.max_sum;


            int sum = sum1 + sum2;
            int max_prefix_sum = max(max_prefix_sum1, sum1 + max_prefix_sum2);
            int max_suffix_sum = max(max_suffix_sum2, sum2 + max_suffix_sum1);
            int max_sum = max( max_suffix_sum1 + max_prefix_sum2, max(max_sum1, max_sum2) );


            return {sum, max_prefix_sum, max_suffix_sum, max_sum};
        }
    }

public:
    SegmentTree(int n, Node *pnodes) {
        __n = n;
        __nodes = pnodes;
        __nodes[0] = {0, n - 1, 0, 0, 0, 0};

        for (int i = 0; i < __n << 2; i++) {
            if (__nodes[i].start == __nodes[i].end and __nodes[i].end == __n - 1) {
                break;
            }

            int mid = (__nodes[i].start + __nodes[i].end) / 2;
            __nodes[i * 2 + 1] = {__nodes[i].start, mid, 0, 0, 0, 0};
            __nodes[i * 2 + 2] = {mid + 1, __nodes[i].end, 0, 0, 0, 0};
        }
    }

    // 更新单个数据接口
    void update_single(int pos, int val) {
        __update_single(0, pos, val);
    }

    // 获取区间统计数据接口
    int get_val(int start, int end) {
        return __get_val(0, start, end).max_sum;
    }
};


int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);
    int n, m, val;
    scanf("%d %d", &n, &m);


    SegmentTree tree(n, __global_nodes);
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        tree.update_single(i, val);
    }

    int cmd, val1, val2;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &cmd, &val1, &val2);

        if (cmd == 1) {
            if (val1 > val2) {
                int t = val1; val1 = val2; val2 = t;
            }

            printf("%d\n", tree.get_val(val1-1, val2-1));
        } else {
            tree.update_single(val1-1, val2);
        }

    }

    return 0;
}