求区间最大值

//顶级垃圾程序
//A very bad program
//Segment Tree
#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE = 1e5 + 5;
struct node{
	int value;
	int lazy = 0; //对这是一个懒标记 
}tree[MAXSIZE * 4];
void build_tree(const int nums[], node tree[], int i, int left, int right){//数据,存的地方,下标,当前区间左右边界 
	if (left == right){ //叶子节点 
		tree[i].value = nums[left];
		return;
	}
	int mid = left + (right - left) / 2;
	build_tree(nums, tree, 2 * i, left, mid); //向左递归建立 
	build_tree(nums, tree, 2 * i + 1, mid + 1, right); //向右递归建立
	tree[i].value = max(tree[2 * i].value, tree[2 * i + 1].value); //更新节点值 
}
//处理懒标记 
void pushDown(node tree[], int i){
	if (tree[i].lazy != 0){
		//更新左边 
		tree[2 * i].value += tree[i].value;
		tree[2 * i].lazy += tree[i].lazy;
		//更新右边 
		tree[2 * i + 1].value += tree[i].value;
		tree[2 * i + 1].lazy += tree[i].lazy;
		//清空懒标记 
		tree[i].lazy = 0;
	}
}
//查询最大值
int query(node tree[], int i, int left, int right, int ql, int qr){ //ql表区间左边界,qr表区间右边界 
	if (ql > right || qr < left) {//越界了 
		return INT_MIN; //无交集，返回其他值 
	}
	if (ql <= right || qr >= left){//区间完全包含在查询区间内
		return tree[i].value; //完了 
	}
	int mid = left + (right - left) / 2;
	pushDown(tree, i);
	int leftMax = query(tree, 2 * i, left, mid, ql, qr); //查询左子树
	int rightMax = query(tree, 2 * i + 1, mid + 1, right, ql, qr); //查询右子树
	return max(leftMax, rightMax); //返回之中的较大值 
} 
//单点更新 
void update(node tree[], int i, int left, int right, int idx, int value){ //idx:元素位置，value:要改成的值 
	if (left == right){
		tree[i].value = value;
		tree[i].lazy = 0; //找到目标节点，更新
		return; 
	} 
	int mid = left + (right - left) / 2;
	pushDown(tree, i); //处理 
	if (idx <= mid){
		update(tree, i * 2, left, mid, idx, value); //更新左边 
	}else{
		update(tree, i * 2 + 1, mid + 1, right, idx, value); //更新右边
	}
	tree[i].value = max(tree[2 * i].value, tree[2 * i + 1].value); //更新节点值 
}
//区间更新
void updateRange(node tree[], int i, int left, int right, int ul, int ur, int value){ //ul,ur与上面同理 
	if (ul > right || ur < left){
		return; //区间无交集，直接返回 
	}
	if (ul <= left && ur >= right){
		tree[i].value += value;//更新当前节点的值 
		tree[i].lazy += value; //设置懒标记
		return; 
	}
	int mid = left + (right - left) / 2;
	pushDown(tree, i);//设置懒标记
	updateRange(tree, 2 * i, left, mid, ul, ur, value); //更新左边
	updateRange(tree, 2 * i + 1, mid + 1, right, ul, ur, value); //更新右边
	tree[i].value = max(tree[2 * i].value, tree[2 * i + 1].value); //更新当前节点的值  
}
int main(){

	return 0;
}

求和

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 5;
struct node{
	ll s, lazy;
	int l, r; //所代表的区间 
	void add(ll x){
		s += x * (r - l + 1);
		lazy += x;
	}
}tree[MAXN * 4];
ll arr[MAXN], n, m, k;
int op, x, y;
void PushDown(int i){
	tree[i << 1].add(tree[i].lazy); //左子树加 
	tree[i << 1 | 1].add(tree[i].lazy);//右边
	tree[i].lazy = 0; //清空 
}
void PushUp(int i){
	tree[i].s = tree[i << 1].s + tree[i << 1 | 1].s; //往上传,当前的和等于左边的和加右边的 
}
//建树 
void build_tree(int i, int l, int r){
	tree[i].l = l;
	tree[i].r = r;
	tree[i].s = tree[i].lazy = 0;
	if(l == r){ //叶子 
		tree[i].s = arr[l];
	}else{
        int mid = (l + r) >> 1;
        build_tree(i << 1, l, mid); //往左 
        build_tree(i << 1 | 1, mid + 1, r); //往右 
        PushUp(i);
    }
}
//加 
void update(int i, int l, int r, ll value){
    int L = tree[i].l, R = tree[i].r;
    if(l <= L && R <= r){
		tree[i].add(value);
	}else{
        PushDown(i);
        int mid = (L + R) >> 1;
        if(mid >= l)
            update(i << 1, l, r, value);
        if(mid<r)
            update(i << 1 | 1, l, r, value);
        PushUp(i);
    }
}
//求和 
ll query(int i, int l, int r){
    int L = tree[i].l, R = tree[i].r;
    if(l <= L && R <= r)
        return tree[i].s;
    PushDown(i);
    int mid = (L + R) >> 1;
    ll ans = 0;
    if(mid >= l)
        ans += query(i << 1, l, r);
    if(mid < r)
        ans += query(i << 1 | 1, l, r);
    PushUp(i);
    return ans;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	build_tree(1, 1, n);
	while (m--){
		cin >> op >> x >> y;
		if (op == 1){
			cin >> k;
			update(1, x, y, k);
		}else{
			cout << query(1, x, y) << endl;
		}
	}
	return 0;
}

例题：P3372 【模板】线段树 1 - 洛谷