<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
线段树
先不考虑这个问题出现在什么题单中,如果赤裸裸的给出了这么一个问题,各位会如何考虑?
相信大部分人应该都会联想到动态规划部分的“最大子数组和”,用线性时间的一般动态规划方法求,但是本问题的序列长度和查询次数都决定了,线性时间都远远超限,需要想到一个办法来优化这个线性的时间复杂度
仔细分析一下最大子段和产生的方式,发现它可能来自于一段前缀$(prefix)$或者后缀$(suffix)$,也可能来自于中间的一段。如果来自于中间的一段,那么将区间进行合理拆分,中间的这一段又可以由一个前缀和一个后缀拼接而成(如上图所示)这种隐含着通过区间合并来转移状态的动态规划问题,可以使用线段树进行辅助
线段树原理就不赘述了, incra之前的帖子 讲的还挺详细的,这里主要来介绍一下需要转移的有哪些状态信息:
首先,既然经过一系列的拆分后,中间区段可以拆分为某些小区间的前/后缀,那每个区间的前后缀最大子段和就需要被维护了,其次是区间总体的最大子段和$totalMaxSum$,产生方式如下图所示:
最后,就是区间自身的和$selfSum$,至于为什么要维护这个,来看前后缀最大和$prefixMaxSum$以及$suffixMaxSum$如何产生便知:
易知前后缀最大和转移的时候,划分出的小区间整体也有可能对大区间产生影响
搞明白了需要维护哪些值,就可以考虑怎么修改和查询了
修改和一般线段树差不多,按照一般的单个位置修改去实现update函数就可
查询这里和一般的有所不一样,需要分三种情况讨论:
二分区间后,如果整个待查区间处于左半边,那就查找左子树,如果整个待查区间处于右半边,那就查找右子树,而对于横跨在中间的,我们需要分别查找左右两边然后合并,这个时候构造临时节点,当作是当前区间代表的节点,然后借用一下pushUp函数,就可以把左右两边的信息合并到当前节点中了(临时节点的$totalMaxSum$就是结果),因此,pushUp需要传入的参数为三个节点,查询函数$getMaxSubsequenceSum$的返回值也得是节点
其余的见注释,另外对于注释中“逻辑位置”和“物理位置”做个解释:
物理位置指的是原序列中某元素处在的位置(下标),逻辑位置是在序列上构造线段树后,操作主体的节点在节点表中所处的位置(下标),和计算机内存管理的“逻辑地址”和“物理地址”含义相似
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
using namespace std;
using _LL = long long;
struct SegmentTreeNode {
int left, right; //左右端点(用确定的序列给出,建议采用顺序存储)
_LL prefixMaxSum, //前缀最大子段和
suffixMaxSum, //后缀最大子段和
totalMaxSum, //区间内最大子段和
selfSum; //自身区间和
//默认构造全0
SegmentTreeNode() :
left(0), right(0),
prefixMaxSum(0), suffixMaxSum(0),
totalMaxSum(0), selfSum(0) {}
};
class SegmentTree {
private:
int* arr;
SegmentTreeNode* base;
//参数为:逻辑位置id,物理位置(区间[l, r])
void buildTree(int id, int l, int r) {
SegmentTreeNode& cur = base[id];
cur.left = l;
cur.right = r;
cur.prefixMaxSum = cur.suffixMaxSum
= cur.selfSum = cur.totalMaxSum
= arr[l]; //以上这些是统一的,但只有l,r相等时才有意义
if (l == r) return;
int mid = (l + r) / 2; //l,r不相等,将区间[l, r]分而治之
buildTree(2 * id, l, mid); //二分区间后,对左右两边递归构造
buildTree(2 * id + 1, mid + 1, r);
pushUp(base[id], base[2 * id], base[2 * id + 1]); //最后将区间和信息向上传递
}
//上传信息到cur节点
void pushUp(SegmentTreeNode& cur, //当前节点
SegmentTreeNode& left, //左孩子
SegmentTreeNode& right) //右孩子
{
cur.selfSum = left.selfSum + right.selfSum; //自身区间和累加
cur.prefixMaxSum = max(
left.prefixMaxSum, left.selfSum + right.prefixMaxSum //确保前缀性质
);
cur.suffixMaxSum = max(
right.suffixMaxSum, right.selfSum + left.suffixMaxSum //确保后缀性质
);
cur.totalMaxSum = max({ //三项取最大
left.totalMaxSum, right.totalMaxSum, //左右孩子的最大区间和
left.suffixMaxSum + right.prefixMaxSum //左后缀+右前缀
});
}
//修改的内核函数
//参数为:逻辑位置id,物理位置pos,目标值target
void _update(int id, int pos, int target) {
SegmentTreeNode& cur = base[id];
if (cur.left == pos && cur.right == pos) { //左右端点都是pos,代表找到目标位置了
cur.prefixMaxSum = cur.suffixMaxSum
= cur.selfSum = cur.totalMaxSum
= target; //当场修改为目标值target
return;
}
int mid = (cur.left + cur.right) / 2; //没找到,继续分而治之
if (pos <= mid) _update(2 * id, pos, target); //在哪一半边就进入哪一侧的子树中
else _update(2 * id + 1, pos, target);
pushUp(base[id], base[2 * id], base[2 * id + 1]); //修改完依旧要向上传递信息
}
//查找的内核函数,直接返回节点本身
//参数为:逻辑位置id,物理位置(区间[l, r])
SegmentTreeNode _query(int id, int l, int r) {
SegmentTreeNode& cur = base[id];
if (cur.left >= l && cur.right <= r) return cur; //被待查区间包含,返回当前节点
int mid = (cur.left + cur.right) / 2; //分而治之,不过要分三种情况
if (r <= mid) { //整个区间位于左侧
return _query(2 * id, l, r); //进入左子树
}
else if (l > mid) { //整个区间位于右侧
return _query(2 * id + 1, l, r); //进入右子树
}
else { //区间横跨左右两边
SegmentTreeNode leftSide
= _query(2 * id, l, r);
SegmentTreeNode rightSide
= _query(2 * id + 1, l, r); //先求得左右两边对应节点
SegmentTreeNode res; //然后构造临时节点
pushUp(res, leftSide, rightSide); //两边信息上传给它
return res; //最后返回它本身
}
}
public:
//构造函数,参数为原序列长度n
SegmentTree(int n) {
int length = 4 * n + 5;
arr = new int[length]; //arr和base都构造4倍长度
fill(arr, arr + length, 0); //C++20前不能直接初始化,要用fill函数
base = new SegmentTreeNode[length];
for (int i = 1; i <= n; i++) {
cin >> arr[i]; //输入原序列
}
buildTree(1, 1, n); //构造线段树结构
}
//按照规范,需要写析构函数,其中的delete和构造函数中new相对应
~SegmentTree() {
delete[] arr;
delete[] base;
}
//将某一个确定位置pos修改为目标值target
void update(int pos, int target) {
_update(1, pos, target);
}
//取得区间[l, r]上的最大子段和
_LL getMaxSubsequenceSum(int l, int r) {
return _query(1, l, r).totalMaxSum;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
SegmentTree ST(n);
while (m--) {
int k, x, y;
cin >> k >> x >> y;
if (k == 2) {
//修改
ST.update(x, y);
}
else {
//查询
if (x > y) swap(x, y);//区间左右端点可能反过来
cout << ST.getMaxSubsequenceSum(x, y) << endl;
}
}
return 0;
}