线段树模板

单点修改，区间查询和

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
struct node{
    int l,r;
    int data;
    #define lson(p) p * 2
    #define rson(p) p * 2 + 1
}tree[maxn<<2];
void pushup(int p){
    tree[p].data = tree[lson(p)].data + tree[rson(p)].data;
}
void bulid(int p,int l,int r){
    tree[p].l = l,tree[p].r = r;
    if(r == l){
        tree[p].data = read();
        return;
    }
    int mid = (l + r)>>1;
    bulid(lson(p),l,mid);
    bulid(rson(p),mid+1,r);
    pushup(p);
}
void add(int p,int x,int c){
    if(tree[p].l == tree[p].r){
        tree[p].data += c;
        return;
    }
    int mid = (tree[p].l + tree[p].r)>>1;
    if(x <= mid)add(lson(p),x,c);
    else add(rson(p),x,c);
    pushup(p);
}
int query(int p,int l,int r){
    if(l <= tree[p].l && tree[p].r <= r)return tree[p].data;
    int mid = (tree[p].l + tree[p].r)>>1;
    int ans = 0;
    if(l <= mid)ans += query(lson(p),l,r);
    if(r > mid)ans += query(rson(p),l,r);
    return ans;
}
int main(){
    int n=read(),m=read();
    bulid(1,1,n);
    int q,l,r,c;
    while(m--){
        q = read();
        if(q == 1){//单点修改
            l = read(),c = read();
            add(1,l,c);
        }else if(q == 2){
            l = read(),r = read();
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

单点修改，区间查询最值

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
struct node{
    int l,r;
    int data;
    #define lson(p) p << 1
    #define rson(p) p << 1 | 1
}tree[maxn<<2];
void pushup(int p){
    tree[p].data = max(tree[lson(p)].data, tree[rson(p)].data);
}
void bulid(int p,int l,int r){
    tree[p].l = l,tree[p].r = r;
    if(r == l){
        tree[p].data = read();
        return;
    }
    int mid = (l + r)>>1;
    bulid(lson(p),l,mid);
    bulid(rson(p),mid+1,r);
    pushup(p);
}
void add(int p,int x,int c){
    if(tree[p].l == tree[p].r){
        tree[p].data += c;
        return;
    }
    int mid = (tree[p].l + tree[p].r)>>1;
    if(x <= mid)add(lson(p),x,c);
    else add(rson(p),x,c);
    pushup(p);
}
int query(int p,int l,int r){
    if(l <= tree[p].l && tree[p].r <= r)return tree[p].data;
    int mid = (tree[p].l + tree[p].r)>>1;
    int ans = 0;
    if(l <= mid)ans = max(query(lson(p),l,r), ans);
    if(r > mid) ans  = max(query(rson(p),l,r), ans);
    return ans;
}
int main(){
    int n=read(),m=read();
    bulid(1,1,n);
    int q,l,r,c;
    while(m--){
        q = read();
        if(q == 1){//单点修改
            l = read(),c = read();
            add(1,l,c);
        }else if(q == 2){
            l = read(),r = read();
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}