#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <functional>
#define PI acos(-1)
#define eps 1e-8
#define inf 0x3f3f3f3f
#define debug(x) cout<<"---"<<x<<"---"<<endl
typedef long long ll;
using namespace std;
#define maxn 200005 //元素总个数
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
int Sum[maxn << 2], Add[maxn << 2]; //Sum求和,Add为懒惰标记
int A[maxn], n; //存原数组数据下标[1,n]
///建树:Build(1,n,1);
//PushUp函数更新节点信息 ,这里是求和
void PushUp(int rt)
{
Sum[rt] = max(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]; //储存数组值
return;
}
int m = (l + r) >> 1;
//左右递归
Build(l, m, rt << 1);
Build(m + 1, r, rt << 1 | 1);
//更新信息
PushUp(rt);
}
///点修改,假设A[L]+=C: Update(L,C,1,n,1);
void Update(int L, int C, int l, int r, int 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)
{
//ln,rn为左子树,右子树的数字数量。
if (Add[rt])
{
//下推标记
Add[rt << 1] += Add[rt];
Add[rt << 1 | 1] += Add[rt];
//修改子节点的Sum使之与对应的Add相对应
Sum[rt << 1] += Add[rt] * ln;
Sum[rt << 1 | 1] += Add[rt] * rn;
//清除本节点标记
Add[rt] = 0;
}
}
///然后是区间查询的函数:int ANS=Query(L,R,1,n,1); ^^^^^^^^^^查询[L,R]区间的最大/最小值^^^^^^^^^^^^^
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;
//下推标记,否则Sum可能不正确
PushDown(rt, m - l + 1, r - m);
//累计答案
int ANS = 0;
if (L <= m)
{
ANS = max(ANS, Query(L, R, l, m, rt << 1));
}
if (R > m)
{
ANS = max(ANS, Query(L, R, m + 1, r, rt << 1 | 1));
}
return ANS;
}
版权声明:本文为GreatJames原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。