线段树可以在 n*logn 的时间复杂度内实现单点修改、区间 修改、区间查询（区间求和，求区间最大值，求区间最小值） 等操作。
在这里顺便把树状数组附上，树状数组只能区间求和时间复杂度也是n*log n
code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n, m;
int a[N], tr[N];int lowbit(int x)
{return x & -x;
}void add(int x, int v)//这个原理很烦，但是你休息只有后面的树状数组才会包含x
{for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}int query(int x)//其实lowbit(i)就表示tr[i]所包含的元素个数
{int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) add(i, a[i]);while (m -- ){int k, x, y;scanf("%d%d%d", &k, &x, &y);if (k == 0) printf("%d\n", query(y) - query(x - 1));else add(x, y);}return 0;
}
B - 敌兵布阵
模板维护区间和
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3fusing namespace std;const int N=2e5+10;
int w[N];
struct node{int l,r;int maxv;
}tr[4*N];
int n,m;void build(int u,int l,int r){if(l==r){tr[u]={l,r,w[l]};}else{tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);}
}void modify(int u,int x,int val){if(tr[u].l==tr[u].r) tr[u].maxv=val;else{int mid= tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,val);else modify(u<<1|1,x,val);tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);}
}int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxv;else{int mid=tr[u].l+tr[u].r>>1;int maxx=-INF;if(l<=mid) maxx =max(maxx, query(u<<1,l,r));if(r>mid) maxx =max(maxx,query(u<<1|1,l,r));return maxx;}
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++) scanf("%d",&w[i]);int a,b;char ch;build(1,1,n);while(m--){scanf(" %c%d%d",&ch,&a,&b);//%c和%d同时输入时%c前面加个空格 if(ch=='U') modify(1,a,b);else printf("%d\n",query(1,a,b));}}return 0;}
D - I Hate It
模板维护区间最大值
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3fusing namespace std;const int N=2e5+10;
int w[N];
struct node{int l,r;int maxv;
}tr[4*N];
int n,m;void build(int u,int l,int r){if(l==r){tr[u]={l,r,w[l]};}else{tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);}
}void modify(int u,int x,int val){if(tr[u].l==tr[u].r) tr[u].maxv=val;else{int mid= tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,val);else modify(u<<1|1,x,val);tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);}
}int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxv;else{int mid=tr[u].l+tr[u].r>>1;int maxx=-INF;if(l<=mid) maxx =max(maxx, query(u<<1,l,r));if(r>mid) maxx =max(maxx,query(u<<1|1,l,r));return maxx;}
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++) scanf("%d",&w[i]);int a,b;char ch;build(1,1,n);while(m--){scanf(" %c%d%d",&ch,&a,&b);//%c和%d同时输入时%c前面加个空格 if(ch=='U') modify(1,a,b);else printf("%d\n",query(1,a,b));}}return 0;}