rt,P3372【模板】线段树 1 求助
代码如下,因 RE 而爆零,
报错显示 Segmentation fault with invalid memory reference即内存引用无效的分段错误。
求调
#include <iostream>
#include <cmath>
#define int long long
using namespace std ;
const int N = 1e7 ;
int n, m ;
int num[N] ;
int way, l, r, x ;
struct Node_tree {
int l, r ;
int maxn, sum ;
int lazy ;
} tree[4 * N + 5] ;
//建线段树
void build(int id, int l, int r) {
tree[id].l = l ; tree[id].r = r ;
if(l == id && r == id) { // 对叶子结点的特判
tree[id].sum = num[id] ;
} else {
register int mid = (l + r) >> 1 ;
build(id * 2, l, mid) ; //建造左子树
build(id * 2 + 1, mid + 1, r) ; //建造右子树
}
}
//数据上传
void push_up(int id) {
tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum ;
tree[id].maxn = max(tree[id * 2].maxn, tree[id * 2 + 1].maxn) ;
}
//数据下传
void push_down(int id, int l, int r) {
if(tree[id].lazy >= 0) { //若 lazy标记存在
register int mid = (l + r) >> 1 ;
tree[id * 2].lazy += tree[id].lazy ; //更新左子树 lazy值
tree[id * 2 + 1].lazy += tree[id].lazy ; //更新右子树 lazy值
tree[id * 2].sum += tree[id].lazy * (mid - l + 1) ; // 更新左子树 sum值
tree[id * 2 + 1].sum += tree[id].lazy * (r - mid) ; // 更新右子树 sum值
tree[id * 2].maxn += tree[id].lazy * (mid - l + 1) ; // 更新左子树 max值
tree[id * 2 + 1].maxn += tree[id].lazy * (r - mid) ; // 更新右子树 max值
}
}
//区间修改
void change(int id, int l, int r, int x) {
//当前到了编号为 id 的节点,要把 [l..r] 区间中的所有元素的值 +x
if(l <= tree[id].l && r >= tree[id].r) {
//如果当前节点的区间被完全包含于要更新的区间内
tree[id].sum += (tree[id].r - tree[id].l + 1) * x ; //更新该区间的 sum
tree[id].lazy += x ; // lazy标记叠加
return ;
}
push_down(id, tree[id].l, tree[id].r) ;
register int mid = (tree[id].l + tree[id].r) >> 1 ;
if(l <= mid) change(id * 2, l, r, x) ; //如果左子树与需要更新的区间有交集
if(r > mid) change(id * 2 + 1, l, r, x) ;//如果右子树与需要更新的区间有交集
push_up(id) ; //更新父节点
}
//区间查询
int query(int id, int l, int r) {
//当前到了编号为 id 的节点,查询 [l..r] 的和
if(l <= tree[id].l && r > tree[id].r) return tree[id].sum ; //如果当前区间完全包含于查询区间,那么直接返回
push_down(id, l, r) ; // 每次访问都去检查lazy标记
register int res = 0 ;
register int mid = (l + r) >> 1 ;
if(l <= mid) res += query(id * 2, l, r) ; //如果左子区间与查询区间有交集
if(r <= mid) res += query(id * 2 + 1, l, r) ; //如果右子区间与查询区间有交集
return res ;
}
signed main ( ) {
cin >> n >> m ;
for(register int i = 1 ; i <= n ; i ++)
cin >> num[i] ;
build(1, 1, n) ;
for(register int i = 1 ; i <= m ; i ++) {
cin >> way >> l >> r ;
if(way == 1) {
cin >> x ;
change(1, l, r, x) ;
} else if(way == 2)
cout << query(1, l, r) << '\n' ;
}
return 0 ;
}