线段树基础学习笔记

线段树

线段树,运用了分治的方法,将一个数组拆成了一堆区间。

线段树和普通的树的区别在于普通的树是维护数,而线段树是维护区间。

我们一般用数组表示法实现二叉树。

见图:

建树

首先,我们从根开始递归,如果当前节点是叶子节点,那么让这个节点等于 $l$,否则递归左右子树,然后更新节点。

pushdown

这个操作是线段树的精华。

这个操作意在维护懒标记并下传标记至子树。

  1. 把标记传到子树。
  2. 通过标记乘长度对子树的值进行操作。
  3. 清空标记。

区间修改

主要思路就是找到目标区间进行操作。

我们定义 $x$ 为需要加的数。

从根节点进行递归,如果目前的区间和目标区间完全没有相交的地方,直接返回。

如果存在包含关系,那么直接加上维护的区间长度 $x$,因为我们需要把区间的每个数都加 $x$。

如果相交,但是不包含,那么我们先 pushdown,然后把目前区间拆分成两个继续往子树去寻找。

最后更新节点。

区间查询

基本上就和修改一样。

区间查询在查询到目标区间后不是修改,而是直接返回数据。

代码

/*

 problem :
 by : ztrztr(luogu 602124)
 date : 2022/10/16
 update : 2022/10/16

*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int seg[1000005], n, mark[1000005], a[1000005];
namespace fun{
    void pd(int nw, int len) {
        mark[nw * 2] += mark[nw];
        mark[nw * 2 + 1] += mark[nw];
        //Update mark.
        seg[nw * 2] += mark[nw] * (len - len / 2);
        seg[nw * 2 + 1] += mark[nw] * (len / 2);
        //Update SegTree.
        mark[nw] = 0;
        //Free mark.
    }
    void build(int nw, int l, int r) {
        if (l == r) {
            seg[nw] = a[l];
            //Leaf node.
//          cout << "[Debug] Finded leaf node " << nw << "\n";
            return; 
        }
        int mid = (l + r) / 2;
//        cout << "11\n";
        build(nw * 2, l, mid);
        build(nw * 2 + 1, mid + 1, r);
        seg[nw] = seg[nw * 2] + seg[nw * 2 + 1];
        //update
    }
    void update(int l, int r, int nw, int x, int nl, int nr) {
        if (nl > r || nr < l) return;
        if (nl >= l && nr <= r) {
            seg[nw] += (nr - nl + 1) * x;
            if (nr > nl) mark[nw] += x;
            return;
        }
        pd(nw, nr - nl + 1);
        update(l, r, nw * 2, x, nl, (nl + nr) / 2);
        update(l, r, nw * 2 + 1, x, (nl + nr) / 2 + 1, nr);
        seg[nw] = seg[nw * 2] + seg[nw * 2 + 1];
        //update
    }
    int find(int l, int r, int nw, int nl, int nr) {
        if (nl > r || nr < l) return 0;
        if (nl >= l && nr <= r) return seg[nw];
        pd(nw, nr - nl + 1);
        int leftAns = find(l, r, nw * 2, nl, (nl + nr) / 2);
        int rightAns = find(l, r, nw * 2 + 1, (nl + nr) / 2 + 1, nr);
        return leftAns + rightAns;
    }
}
using namespace fun;
namespace OI{
    void run() {
        int m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        build(1, 1, n);
//      cout << "[Debug] Build OK!\n";
        while (m --) {
            int op; cin >> op;
            if (op == 1) {
                int x, y, z; cin >> x >> y >> z;
                update(x, y, 1, z, 1, n);
            } else {
                int x, y; cin >> x >> y;
                cout << find(x, y, 1, 1, n) << "\n";
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    OI::run();
    return 0;
}
本文链接:https://ztrztr.top/archives/97
版权声明:本文 《线段树基础学习笔记》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇