一道非常直白的线段树题目，甚至不需要慵懒操作233，如果你不知道什么是线段树，可以去看我的这篇文章：线段树入门

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3
1 2 -1
2 3 -1
3 1 2

样例输出

-1
-2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100005
int arr[MAXN];
struct tr{
    int l, r, mx, sum;
}Tr[MAXN << 2];
void push(int d){
    Tr[d].mx = max(Tr[d << 1].mx, Tr[d << 1 | 1].mx);
    Tr[d].sum = Tr[d << 1].sum + Tr[d << 1 | 1].sum;
}
void build(int l, int r, int d){
    Tr[d].l = l, Tr[d].r = r;
    if(l == r){
        Tr[d].mx = arr[l], Tr[d].sum = arr[l];
        return;
    }
    int mid = (l + r) >> 1, lc = d << 1, rc = d << 1 | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    push(d);
}
void modify(int d, int pos, int v){
    if(Tr[d].l == Tr[d].r && Tr[d].l == pos){
        Tr[d].mx = v, Tr[d].sum = v;
        return;
    }
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(pos <= mid)modify(lc, pos, v);
    else modify(rc, pos, v);
    push(d);
}
int querymx(int l, int r, int d){
    if(Tr[d].l == l && Tr[d].r == r)return Tr[d].mx;
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(r <= mid)return querymx(l, r, lc);  // [L, [l, r], mid, R]
    else if( l > mid )return querymx(l, r, rc);  // [L, mid, [l, r], R]
    else return max(querymx(l, mid, lc), querymx(mid + 1, r, rc));  //[L, [l, mid, r], R]
}
int querysum(int l, int r, int d){
    if(Tr[d].l == l && Tr[d].r == r)return Tr[d].sum;
    int mid = (Tr[d].l + Tr[d].r) >> 1, lc = d << 1, rc = d << 1 | 1;
    if(r <= mid)return querysum(l, r, lc);
    else if( l > mid )return querysum(l, r, rc);
    else return querysum(l, mid, lc)+ querysum(mid + 1, r, rc);
}
int main(){
    int n, m, type, p1, p2;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%d", &arr[i]);
    build(1, n, 1);
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &type, &p1, &p2);
        if(type == 1)modify(1, p1, p2);
        else if(type == 2)printf("%d\n", querysum(p1, p2, 1));
        else printf("%d\n", querymx(p1, p2, 1));
    }
    return 0;
}