题目描述
AcWing 245.你能回答这些问题吗
算法
区间最大子段和,线段树
C++ 代码
#include <iostream>
using namespace std;
int a[500010];
struct node
{
int lmax, rmax, mx, sum;
}tree[2000010];
/**
* @brief 更新父结点
* @return void
*/
void pushup(node& f, node& l, node& r)
{
f.sum = l.sum + r.sum;
f.lmax = max(l.lmax, l.sum + r.lmax);
f.rmax = max(r.rmax, r.sum + l.rmax);
f.mx = max(max(l.mx, r.mx), l.rmax + r.lmax);
}
/**
* @brief 建线段树
* @param now 当前结点
* @param start 维护区间的左端点
* @param end 维护区间的右端点
* @return void
*/
void build(int now, int start, int end)
{
if (start == end)
{
tree[now].lmax = tree[now].rmax = tree[now].mx = tree[now].sum = a[start];
return;
}
int mid = (start + end) / 2;
int left = now * 2 + 1;
int right = now * 2 + 2;
build(left, start, mid);
build(right, mid + 1, end);
pushup(tree[now], tree[left], tree[right]);
return;
}
/**
* @brief 改变a里面的某一个值后更新线段树--单点更新
* @param now 当前结点
* @param start 维护区间的左端点
* @param end 维护区间的右端点
* @param idx 改变元素的下标
* @param val 将a[idx]改为val
* @return void
*/
void update(int now, int start, int end, int idx, int val)
{
if (start == end)
{
a[start] = val;
tree[now].lmax = tree[now].rmax = tree[now].mx = tree[now].sum = a[start];
return;
}
int mid = (start + end) / 2;
int left = now * 2 + 1;
int right = now * 2 + 2;
if (idx <= mid)
update(left, start, mid, idx, val);
else
update(right, mid + 1, end, idx, val);
pushup(tree[now], tree[left], tree[right]);
return;
}
/**
* @brief 求区间的最大子段和
* @param now 当前结点
* @param start 维护区间的左端点
* @param end 维护区间的右端点
* @param L 区间左端点
* @param R 区间右端点
* @return int
*/
node query(int now, int start, int end, int L, int R)
{
if (start >= L && end <= R)
return tree[now];
int mid = (start + end) / 2;
int left = now * 2 + 1;
int right = now * 2 + 2;
if (R <= mid)
return query(left, start, mid, L, R);
else if (L > mid)
return query(right, mid + 1, end, L, R);
else
{
node a = query(left, start, mid, L, R);
node b = query(right, mid + 1, end, L, R);
node c;
pushup(c, a, b);
return c;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (m--)
{
int k, x, y;
cin >> k >> x >> y;
if (k == 1)
{
if (x > y)
swap(x, y);
cout << query(1, 1, n, x, y).mx << endl;
}
else
update(1, 1, n, x, y);
}
return 0;
}
dalao,pushup()中为什么每个变量前加&?
很久没有来刷题了,刚看到。使用引用参数可以直接操作实参变量,比如pushup(tree[now], tree[left], tree[right]);这个调用中,tree[now], tree[left], tree[right]的值都会被改变。再不明白的话就去学一下引用传递。