contents：
本质
二分的应用
前缀和
差分
模板1
点我？: 线段树小白.
只有单点修改和区间查询
1、更新一个点：
将子节点值合并
2、建树
建一棵树就是建左右子树
先从上至下
到达叶子
递归更新
3、修改一个点
修改整体到修改单点越来越细分，直到修改到一个值
最后值变了，也得更新
4、区间求和
相当于遍历完所有区间，如果遍历到的区间完全在分内那就加上，并且结束
和搜索是一样的
整体就是从上至下，再从下至上
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5 + 7;
int sum[N << 2];
int arr[N], n;
//更新求和
void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
//建立线段树
void build(int l, int r, int rt)
{
if (l == r)
{
sum[rt] = arr[l];
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
pushup(rt);
}
//单点修改arr[L]+=C
void updata(int L, int C, int l, int r, int rt)
{
if (l == r)
{
sum[rt] += C;
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
updata(L, C, l, mid, rt<<1);
else
updata(L, C, mid + 1, r, rt<<1|1);
pushup(rt);
}
//区间求和
int query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
{
return sum[rt];
}
int ans = 0;
int mid = (l + r) >> 1;
if (L <= mid)
ans += query(L, R, l, mid, rt<<1);
if(R>mid)
ans += query(L, R, mid + 1, r, rt<<1|1);
return ans;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
build(1, n, 1);
int m;
cin >> m;
while (m--)
{
int index, upvalue;
cin >> index >> upvalue;
updata(index, upvalue, 1, n, 1);
int res = query(index, index, 1, n, 1);
cout << res << endl;
}
system("pause");
return 0;
}
5
1 2 3 4 5
5
1 2
3
2 3
5
3 1
4
5 2
7
1 2
5
模板2
点我！: 线段树本树.
求和
#include <bits/stdc++.h>
using namespace std;
#define maxn 100007 //元素总个数
int Sum[maxn << 2]; //Sum求和，开四倍空间
int add[maxn << 2];
int A[maxn], n; //存原数组下标[1，n]
//PushUp函数更新节点信息，这里是求和
void PushUp(int rt) { Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1]; }
//Build函数建立线段树
void Build(int l, int r, int rt)
{ //[l,r]表示当前节点区间，rt表示当前节点的实际存储位置
if (l == r)
{ //若到达叶节点
Sum[rt] = A[l]; //存储A数组的值
return;
}
int m = (l + r) >> 1;
//左右递归
Build(l, m, rt << 1);
Build(m + 1, r, rt << 1 | 1);
//更新信息
PushUp(rt);
}
void Update(int L, int C, int l, int r, int rt)
{ //[l,r]表示当前区间，rt是当前节点编号//l,r表示当前节点区间，rt表示当前节点编号
if (l == r)
{ //到达叶节点，修改叶节点的值
Sum[rt] = C; //+=,变值//=,修改值//
return;
}
int m = (l + r) >> 1;
//根据条件判断往左子树调用还是往右
if (L <= m)
Update(L, C, l, m, rt << 1);
else
Update(L, C, m + 1, r, rt << 1 | 1);
PushUp(rt); //子节点的信息更新了，所以本节点也要更新信息
}
void Pushdown(int rt, int ln, int rn)
{
if (add[rt])
{
add[rt << 1] += add[rt];
add[rt << 1 | 1] += add[rt];
Sum[rt << 1] += ln * add[rt];
Sum[rt << 1 | 1] += rn * add[rt];
add[rt] = 0;
}
}
void Update(int L, int R, int C, int l, int r, int rt)
{
if (L <= l && r <= R)
{
Sum[rt] += (r - l + 1) * C;
add[rt] += C;
return;
}
int m = (l + r) >> 1;
Pushdown(rt, m - l + 1, r - m);
if (L <= m)
Update(L, R, C, l, m, rt << 1);
if (R > m)
Update(L, R, C, m + 1, r, rt << 1 | 1);
PushUp(rt);
}
int Query(int L, int R, int l, int r, int rt)
{ //[L,R]表示操作区间，[l,r]表示当前区间，rt:当前节点编号
if (L <= l && r <= R)
{
//在区间内直接返回
return Sum[rt];
}
int m = (l + r) >> 1;
Pushdown(rt, m - l + 1, r - m);
//左子区间:[l,m] 右子区间：[m+1,r] 求和区间:[L,R]
//累加答案
int ANS = 0;
if (L <= m)
ANS += Query(L, R, l, m, rt << 1); //左子区间与[L,R]有重叠，递归
if (R > m)
ANS += Query(L, R, m + 1, r, rt << 1 | 1); //右子区间与[L,R]有重叠，递归
return ANS;
}
int main()
{
cout << "n?" << endl;
cin >> n;
cout<<"n*arr[i]?"<<endl;
for (int i = 1; i <= n; i++)
{
cin >> A[i];
}
Build(1, n, 1);
cout << "m?" << endl;
int m;
cin >> m;
while (m--)
{
int L,R, upvalue;
cout << "L?R?V?" << endl;
cin >> L>>R>> upvalue;
Update(L,R, upvalue, 1, n, 1);
cout << "L?R?" << endl;
cin >> L >> R;
int res = Query(L,R, 1, n, 1);
cout << res << endl;
}
system("pause");
return 0;
}
min
#include <bits/stdc++.h>
using namespace std;
#define maxn 100007 //元素总个数
int Sum[maxn << 2]; //Sum求和，开四倍空间
int add[maxn << 2];
int A[maxn], n; //存原数组下标[1，n]
//PushUp函数更新节点信息，这里是求和
void PushUp(int rt) { Sum[rt] = min(Sum[rt << 1], Sum[rt << 1 | 1]); }
//Build函数建立线段树
void Build(int l, int r, int rt)
{ //[l,r]表示当前节点区间，rt表示当前节点的实际存储位置
if (l == r)
{ //若到达叶节点
Sum[rt] = A[l]; //存储A数组的值
return;
}
int m = (l + r) >> 1;
//左右递归
Build(l, m, rt << 1);
Build(m + 1, r, rt << 1 | 1);
//更新信息
PushUp(rt);
}
void Update(int L, int C, int l, int r, int rt)
{ //[l,r]表示当前区间，rt是当前节点编号//l,r表示当前节点区间，rt表示当前节点编号
if (l == r)
{ //到达叶节点，修改叶节点的值
Sum[rt] = C; //+=,变值//=,修改值//
return;
}
int m = (l + r) >> 1;
//根据条件判断往左子树调用还是往右
if (L <= m)
Update(L, C, l, m, rt << 1);
else
Update(L, C, m + 1, r, rt << 1 | 1);
PushUp(rt); //子节点的信息更新了，所以本节点也要更新信息
}
void Pushdown(int rt, int ln, int rn)
{
if (add[rt] != 0)
{
add[rt << 1] += add[rt];
add[rt << 1 | 1] += add[rt];
Sum[rt << 1] += add[rt];
Sum[rt << 1 | 1] += add[rt];
add[rt] = 0;
}
}
void Update(int L, int R, int C, int l, int r, int rt)
{
if (L <= l && r <= R)
{ //在区间内
Sum[rt] += C;
add[rt] += C;
return;
}
int m = (l + r) >> 1;
Pushdown(rt, m - l + 1, r - m);
if (L <= m)
Update(L, R, C, l, m, rt << 1);
if (R > m)
Update(L, R, C, m + 1, r, rt << 1 | 1);
PushUp(rt);
}
int Query(int L, int R, int l, int r, int rt)
{ //[L,R]表示操作区间，[l,r]表示当前区间，rt:当前节点编号
if (L <= l && r <= R)
{
//在区间内直接返回
return Sum[rt];
}
int m = (l + r) >> 1;
Pushdown(rt, m - l + 1, r - m);
//左子区间:[l,m] 右子区间：[m+1,r] 求和区间:[L,R]
//累加答案
int ANS = 0x3f3f3f3f;
if (L <= m)
ANS = min(ANS, Query(L, R, l, m, rt << 1)); //左子区间与[L,R]有重叠，递归
if (R > m)
ANS = min(ANS, Query(L, R, m + 1, r, rt << 1 | 1)); //右子区间与[L,R]有重叠，递归
return ANS;
}
int main()
{
cout << "n?" << endl;
cin >> n;
cout << "n*arr[i]?" << endl;
for (int i = 1; i <= n; i++)
{
cin >> A[i];
}
Build(1, n, 1);
cout << "m?" << endl;
int m;
cin >> m;
while (m--)
{
int L, R, upvalue;
cout << "L?R?V?" << endl;
cin >> L >> R >> upvalue;
Update(L, R, upvalue, 1, n, 1);
cout << "L?R?" << endl;
cin >> L >> R;
int res = Query(L, R, 1, n, 1);
cout << res << endl;
}
system("pause");
return 0;
}
非递归
在这里插入代码片