历时三个月。。。我到底在干什么？？
之前写线段树都是自己瞎写的版本，也是比较繁琐(只是不是递归写法罢了)。这里改成网上的线段树标配版，递归写法，要注意的是递归写法会占用更多的内存，因为递归会使用系统栈。
线段树标配版：结构体数组存树，树根为1，对于每个节点i，其左孩子节点为2*i，右孩子节点为2*i+1(也可以用i<<1, i<<1|1)，那每个节点的父亲节点就是i/2(i>>1)。
递归建树
inline void build(int i, int l, int r){ //在节点i处建立区间为[l, r]的线段树
tree[i].l = l, tree[i].r = r;
if (l==r){
tree[i].sum = nums[l];
return;
}
int mid = (l+r)>>1;
build(i<<1, l, mid); build(i<<1|1, mid+1, r);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
return;
}
//主函数中：
build(1, 1, n);单点修改
可以从下往上，也可以从上往下(需要push_down)。
//从下往上
inline void update(int i, int k){ //从节点i开始往上更新，直到根节点也更新了。
tree[i].value = k; i >>= 1;
while (i){
tree[i].value = max(tree[2*i].value, tree[2*i+1].value);
i >>= 1;
}
return;
}
//从上往下
void update(int i, int target, int k){ //在节点i中寻找下标target并将其值改为k
if (tree[i].l==tree[i].r){
tree[i].value = k;
return;
}
pushdown(i);
if (tree[2*i].r>=target) update(2*i, target, k);
else update(2*i+1, target, k);
tree[i].value = max(tree[2*i].value, tree[2*i+1].value);
return;
}
区间查询
正因为要进行区间操作才会有这个数据结构(不然只有单点操作谁还会用这玩意)。
inline ll search(int i, int l, int r){ //在根为i的子树里查询区间[l, r]的值
if (tree[i].l>=l && tree[i].r<=r){
return tree[i].sum;
}
push_down(i);
ll ans = 0;
if (tree[i<<1].r>=l) ans += search(i<<1, l, r);
if (tree[i<<1|1].l<=r) ans += search(i<<1|1, l, r);
return ans;
}区间修改
这里相当于是线段树的进阶了。。。
引入一个新的思想：lazytag懒惰标记。
因为对区间进行操作(比如这个区间内所有数加上一个数)，我们如果对这个区间每一个数都逐个进行操作的话，是很麻烦很慢的，所以我们可以在这个区间上(假设该区间刚好由一个节点表示)标记一个tag，用来表示对这个区间进行某种操作，但没有具体到每一个元素。
讲一下这个lazytag的特性：比如某个节点i，其表示的区间为[l, r]，然后该结点已经有了懒惰标记lazytag，就是说对区间[l, r]有了某种不可描述的操作，注意这个lazytag只对该结点的孩子节点们有作用，而对其祖宗结点无影响。假设该线段树是求区间求和的树，那么该结点的权值可能不等于其左右孩子的权值和，因为他有个lazytag，但对其祖宗结点，这个lazytag是不起作用的，仍然满足我们最初的设想：结点的权值=左孩子+右孩子权值。
在讲一下push_down操作：该操作就是把一个结点已经标记了的lazytag往下push，传给它的孩子结点。传的时候其实很简单，根据我们对lazytag的定义和属性，合并其孩子结点原有的lazytag和新加上去的lazytag就行了，基本就是这个意思。然后我们什么时候用到pushdown操作呢？比如现在结点i有一个lazytag，但是我们可能要对其子区间进行操作，修改或者访问，我们知道lazytag是对节点的区间作用的，我们要对其子区间操作，必须要考虑这个lazytag带来的影响啊，所以这个时候就要把lazytag进行push_down操作！
终于写完\~
inline void push_down(int i){
if (tree[i].lz){
tree[2*i].lz += tree[i].lz;
tree[2*i+1].lz += tree[i].lz;
tree[2*i].sum += tree[i].lz * (tree[2*i].r-tree[2*i].l+1);
tree[2*i+1].sum += tree[i].lz * (tree[2*i+1].r-tree[2*i+1].l+1);
tree[i].lz = 0;
}
return;
}
inline void add(int i, int l, int r, int k){
if (tree[i].l>=l && tree[i].r<=r){
tree[i].sum += k*(tree[i].r-tree[i].l+1);
tree[i].lz += k;
return;
}
push_down(i);
if (tree[2*i].r>=l) add(2*i, l, r, k);
if (tree[2*i+1].l<=r) add(2*i+1, l, r, k);
tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
return;
}
inline ll search(int i, int l, int r){
if (tree[i].l>=l && tree[i].r<=r){
return tree[i].sum;
}
if (tree[i].l>r || tree[i].r<l) return 0;
push_down(i);
ll ans = 0;
if (tree[2*i].r>=l) ans += search(2*i, l, r);
if (tree[2*i+1].l<=r) ans += search(2*i+1, l, r);
return ans;
}洛谷P3372 【模板】线段树1
本题中lazytag的作用就是对该结点所表示的区间的每一个数都加上一个数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
struct tree{
int l, r;
ll sum;
ll lz;
tree(){
sum = lz = 0;
}
}tree[maxn*4];
int n, m;
ll nums[maxn];
inline void build(int i, int l, int r){
tree[i].l = l, tree[i].r = r;
if (tree[i].l==tree[i].r){
tree[i].sum = nums[l];
return;
}
int mid = (l+r)>>1;
build(i<<1, l, mid); build(i<<1|1, mid+1, r);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
return;
}
inline void push_down(int i){
if (tree[i].lz){
tree[i<<1].lz += tree[i].lz;
tree[i<<1|1].lz += tree[i].lz;
tree[i<<1].sum += tree[i].lz * (tree[i<<1].r-tree[i<<1].l+1);
tree[i<<1|1].sum += tree[i].lz * (tree[i<<1|1].r-tree[i<<1|1].l+1);
tree[i].lz = 0;
}
return;
}
inline void add(int i, int l, int r, int k){
if (tree[i].l>=l && tree[i].r<=r){
tree[i].sum += k*(tree[i].r-tree[i].l+1);
tree[i].lz += k;
return;
}
push_down(i);
if (tree[i<<1].r>=l) add(i<<1, l, r, k);
if (tree[i<<1|1].l<=r) add(i<<1|1, l, r, k);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
return;
}
inline ll search(int i, int l, int r){
if (tree[i].l>=l && tree[i].r<=r){
return tree[i].sum;
}
if (tree[i].l>r || tree[i].r<l) return 0;
push_down(i);
ll ans = 0;
if (tree[i<<1].r>=l) ans += search(i<<1, l, r);
if (tree[i<<1|1].l<=r) ans += search(i<<1|1, l, r);
return ans;
}
int main(){
int flag, x, y, k;
scanf ("%d %d", &n, &m);
for (int i=1; i<=n; i++) scanf ("%lld", nums+i);
build(1, 1, n);
for (int i=1; i<=m; i++){
scanf ("%d", &flag);
if (flag&1){
scanf ("%d %d %d", &x, &y, &k);
add(1, x, y, k);
continue;
}
scanf ("%d %d", &x, &y);
printf ("%lld\n", search(1, x, y));
}
return 0;
}洛谷P3373 【模板】线段树2
这题有两个lazytag，那么如何定义其属性呢？看自已，只要和pushdown操作配套就行。定义两个标记mlz, plz.
这里我定义的是对区间的每个数先乘以mlz，然后再加上plz。合并两个标记的时候要注意如何合并才能不影响其意义。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
struct tree{
int l, r;
ll sum;
ll lz;
tree(){
sum = lz = 0;
}
}tree[maxn*4];
int n, m;
ll nums[maxn];
inline void build(int i, int l, int r){
tree[i].l = l, tree[i].r = r;
if (tree[i].l==tree[i].r){
tree[i].sum = nums[l];
return;
}
int mid = (l+r)>>1;
build(i<<1, l, mid); build(i<<1|1, mid+1, r);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
return;
}
inline void push_down(int i){
if (tree[i].lz){
tree[i<<1].lz += tree[i].lz;
tree[i<<1|1].lz += tree[i].lz;
tree[i<<1].sum += tree[i].lz * (tree[i<<1].r-tree[i<<1].l+1);
tree[i<<1|1].sum += tree[i].lz * (tree[i<<1|1].r-tree[i<<1|1].l+1);
tree[i].lz = 0;
}
return;
}
inline void add(int i, int l, int r, int k){
if (tree[i].l>=l && tree[i].r<=r){
tree[i].sum += k*(tree[i].r-tree[i].l+1);
tree[i].lz += k;
return;
}
push_down(i);
if (tree[i<<1].r>=l) add(i<<1, l, r, k);
if (tree[i<<1|1].l<=r) add(i<<1|1, l, r, k);
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
return;
}
inline ll search(int i, int l, int r){
if (tree[i].l>=l && tree[i].r<=r){
return tree[i].sum;
}
if (tree[i].l>r || tree[i].r<l) return 0;
push_down(i);
ll ans = 0;
if (tree[i<<1].r>=l) ans += search(i<<1, l, r);
if (tree[i<<1|1].l<=r) ans += search(i<<1|1, l, r);
return ans;
}
int main(){
int flag, x, y, k;
scanf ("%d %d", &n, &m);
for (int i=1; i<=n; i++) scanf ("%lld", nums+i);
build(1, 1, n);
for (int i=1; i<=m; i++){
scanf ("%d", &flag);
if (flag&1){
scanf ("%d %d %d", &x, &y, &k);
add(1, x, y, k);
continue;
}
scanf ("%d %d", &x, &y);
printf ("%lld\n", search(1, x, y));
}
return 0;
}
0 条评论