首页 > 其他分享 >数据结构——线段树 入门以后 学习笔记

数据结构——线段树 入门以后 学习笔记

时间：2024-01-19 14:34:46浏览次数：28  
标签：ll return 入门 int 线段 mid query 数据结构 void

数据结构——线段树 入门以后 学习笔记

入门笔记有时间写。

才发现我不会线段树。/ll

可以看出来我很喜欢 class /cf

有的代码需要前置：

using ll = long long;
constexpr ll mod = 998244353;
constexpr int root = 1;

P3372 线段树 1

class seg_t {

private:

struct emm {
    int l, r;
    ll v, lz;
};

int n; vector<emm> a;

void pushup(int k) {
    a[k].v = a[k * 2].v + a[k * 2 + 1].v;
}

void run(int k, ll v) {
    a[k].lz += v;
    a[k].v += v * (a[k].r - a[k].l + 1);
}

void pushdown(int k) {
    if (!a[k].lz) return;
    run(k * 2, a[k].lz);
    run(k * 2 + 1, a[k].lz);
    a[k].lz = 0;
}

void build(vector<ll> &q, int k, int l, int r) {
    a[k].lz = 0, a[k].l = l, a[k].r = r;
    if (l == r) { a[k].v = q[l]; return; }
    int mid = l + (r - l >> 1);
    build(q, k * 2, l, mid);
    build(q, k * 2 + 1, mid + 1, r);
    pushup(k);
}

void modify(int k, const int p, const int q, const ll v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) { run(k, v); return; }
    pushdown(k);
    int mid = l + (r - l >> 1);
    if (mid >= p) modify(k * 2, p, q, v);
    if (mid + 1 <= q) modify(k * 2 + 1, p, q, v);
    pushup(k);
}

ll query(int k, const int p, const int q) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) return a[k].v;
    pushdown(k);
    int mid = l + (r - l >> 1); ll res = 0;
    if (mid >= p) res += query(k * 2, p, q);
    if (mid + 1 <= q) res += query(k * 2 + 1, p, q);
    return res;
}

public:

seg_t(vector<ll> &q) { n = q.size(), a.resize(4 * n); build(q, 1, 1, n); }
void add(int l, int r, ll v) { modify(1, l, r, v); }
ll sum(int l, int r) { return query(1, l, r); }

};

P3373 线段树 2

class seg_t {

private:

struct emm {
    int l, r;
    ll v, ad, ml;
};

int n; vector<emm> a;

void push_up(int k) {
    (a[k].v = a[k * 2].v + a[k * 2 + 1].v) %= mod;
}

void action_add(int k, ll t) {
    (a[k].ad += t) %= mod;
    (a[k].v += t * (a[k].r - a[k].l + 1) % mod) %= mod;
}

void action_mul(int k, ll t) {
    (a[k].v *= t) %= mod;
    (a[k].ad *= t) %= mod, (a[k].ml *= t) %= mod;
}

void push_down(int k) {
    if (a[k].ml != 1) {
        action_mul(k * 2, a[k].ml);
        action_mul(k * 2 + 1, a[k].ml);
        a[k].ml = 1;
    } if (a[k].ad) {
        action_add(k * 2, a[k].ad);
        action_add(k * 2 + 1, a[k].ad);
        a[k].ad = 0;
    }
}

void build(vector<ll> &q, int k, int l, int r) {
    a[k].l = l, a[k].r = r; a[k].ad = 0, a[k].ml = 1;
    if (l == r) { a[k].v = q[l]; return; }
    int mid = l + (r - l >> 1);
    build(q, k * 2, l, mid);
    build(q, k * 2 + 1, mid + 1, r);
    push_up(k);
}

ll query(int k, int p, int q) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) return a[k].v;
    push_down(k); int mid = l + (r - l >> 1);
    ll res = 0;
    if (mid >= p) res += query(k * 2, p, q);
    if (mid + 1 <= q) res += query(k * 2 + 1, p, q);
    return res % mod;
}

void modify_add(int k, int p, int q, ll v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) { action_add(k, v); return; }
    push_down(k); int mid = l + (r - l >> 1);
    if (mid >= p) modify_add(k * 2, p, q, v);
    if (mid + 1 <= q) modify_add(k * 2 + 1, p, q, v);
    push_up(k);
}

void modify_mul(int k, int p, int q, ll v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) { action_mul(k, v); return; }
    push_down(k); int mid = l + (r - l >> 1);
    if (mid >= p) modify_mul(k * 2, p, q, v);
    if (mid + 1 <= q) modify_mul(k * 2 + 1, p, q, v);
    push_up(k);
}

public:

seg_t(vector<ll> &q) { n = q.size(); a.resize(n * 4); build(q, root, 1, n); }
ll sum(int l, int r) { return query(root, l, r); }
void add(int l, int r, ll v) { modify_add(root, l, r, v); }
void mul(int l, int r, ll v) { modify_mul(root, l, r, v); }

};

CF438D The Child and Sequence

取模的两个定理。一个是不取模，一个是取了小于一半。

class seg_t {

private:

struct emm {
    int l, r;
    ll v, mx;
};

int n; vector<emm> a;

void push_up(int k) {
    a[k].v = a[k * 2].v + a[k * 2 + 1].v;
    a[k].mx = max(a[k * 2].mx, a[k * 2 + 1].mx);
}

void build(vector<ll> &q, int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if (l == r) { a[k].v = a[k].mx = q[l]; return; }
    int mid = l + (r - l >> 1);
    build(q, k * 2, l, mid);
    build(q, k * 2 + 1, mid + 1, r);
    push_up(k);
}

ll query(int k, int p, int q) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) return a[k].v;
    int mid = l + (r - l >> 1); ll res = 0;
    if (mid >= p) res += query(k * 2, p, q);
    if (mid + 1 <= q) res += query(k * 2 + 1, p, q);
    return res;
}

void modify(int k, int x, ll v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l == r) { a[k].v = a[k].mx = v; return; }
    int mid = l + (r - l >> 1);
    if (x <= mid) modify(k * 2, x, v);
    else modify(k * 2 + 1, x, v);
    push_up(k);
}

void putmod(int k, int p, int q, ll m) {
    auto &l = a[k].l, &r = a[k].r;
    if (l == r) { a[k].v = a[k].mx = a[k].v % m; return; }
    int mid = l + (r - l >> 1);
    if (mid >= p && a[k * 2].mx >= m) putmod(k * 2, p, q, m);
    if (mid + 1 <= q && a[k * 2 + 1].mx >= m) putmod(k * 2 + 1, p, q, m);
    push_up(k);
}

public:

seg_t(vector<ll> &q) { n = q.size(); a.resize(n * 4); build(q, root, 1, n); }
ll sum(int l, int r) { return query(root, l, r); }
void mod(int l, int r, ll x) { putmod(root, l, r, x); }
void change(int k, ll x) { modify(root, k, x); }

};

SP1043 GSS1 & SP1716 GSS3 & SP2916 GSS5

class seg_t {

private:

struct v_t {
    int prefix, suffix; int sum, res;
    void set(const int x) { prefix = suffix = sum = res = x; }
    friend v_t operator+ (const v_t &a, const v_t &b) {
        v_t res; res.sum = a.sum + b.sum;
        res.prefix = max(a.prefix, a.sum + b.prefix);
        res.suffix = max(b.suffix, b.sum + a.suffix);
        res.res = max(max(a.res, b.res), a.suffix + b.prefix);
        return res;
    }
};

struct emm { int l, r; v_t v; };

int n; vector<emm> a;

void push_up(int k) {
    a[k].v = a[k * 2].v + a[k * 2 + 1].v;
}

void build(vector<int> &q, int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if (l == r) { a[k].v.set(q[l]); return; }
    int mid = l + (r - l >> 1);
    build(q, k * 2, l, mid);
    build(q, k * 2 + 1, mid + 1, r);
    push_up(k);
}

void modify(int k, int x, int v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l == r) { a[k].v.set(v); return; }
    int mid = l + (r - l >> 1);
    if (x <= mid) modify(k * 2, x, v);
    else modify(k * 2 + 1, x, v);
    push_up(k);
}

v_t query(int k, int p, int q) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) return a[k].v;
    int mid = l + (r - l >> 1);
    if (mid < p) return query(k * 2 + 1, p, q);
    if (mid + 1 > q) return query(k * 2, p, q);
    return query(k * 2, p, q) + query(k * 2 + 1, p, q);
}

public:

seg_t(vector<int> &q) { n = q.size(); a.resize(4 * n); build(q, root, 1, n); }
int mis(int l, int r) { return query(root, l, r).res; }
int sum(int l, int r) { return query(root, l, r).sum; }
int pre(int l, int r) { return query(root, l, r).prefix; }
int suf(int l, int r) { return query(root, l, r).suffix; }
void change(int x, int v) { modify(root, x, v); }

};

void solve(int n) {
    vector<int> a(n + 1);
    rep(i, n) a[i + 1] = rr;
    int m = ur; seg_t seg(a);
    auto query = [&] (int l1, int r1, int l2, int r2) {
        if (l1 == r1 && r1 == r2) return seg.mis(l1, r2);
        if (r1 < l2) return seg.sum(r1 + 1, l2 - 1) + seg.suf(l1, r1) +
                                                      seg.pre(l2, r2);
        int ans = seg.mis(l2, r1);
        if(l1 < l2) ans = max(ans, seg.suf(l1, l2) + seg.pre(l2, r2) - a[l2]);
        if(r2 > r1) ans = max(ans, seg.suf(l1, r1) + seg.pre(r1, r2) - a[r1]);
        return ans;
    }; while (m--) {
        int l1 = ur, r1 = ur, l2 = ur, r2 = ur;
        printf("%d\n", query(l1, r1, l2, r2));
    }
}

P1253 扶苏的问题

曾经写的代码。和现在的线段树风格不一样。

template<typename tp, tp INIT>
class segment {
#define mid ((l + r) >> 1)
#define vp vector<tp>
private:
    int n; vp s, mad, mre;
    void _build(int k, int l, int r, vp &a) {
        if (l == r) { s[k] = a[l]; return; }
        _build(k * 2, l, mid, a), _build(k * 2 + 1, mid + 1, r, a);
        s[k] = max(s[k * 2], s[k * 2 + 1]);
    } void _addmad(int k, tp x) {
        s[k] += x;
        if (mad[k] == -INIT) mad[k] = x;
        else mad[k] += x;
    } void _addmre(int k, tp x) {
        s[k] = mre[k] = x, mad[k] = -INIT;
    } void _pushdown(int k) {
        if (mre[k] != -INIT) _addmre(k * 2, mre[k]), _addmre(k * 2 + 1, mre[k]), mre[k] = -INIT;
        if (mad[k] != -INIT) _addmad(k * 2, mad[k]), _addmad(k * 2 + 1, mad[k]), mad[k] = -INIT;
    } void _add(int k, int l, int r, int p, int q, tp x) {
        if (r < p || l > q) return;
        if (l >= p && r <= q) { _addmad(k, x); return; }
        _pushdown(k); _add(k * 2, l, mid, p, q, x), _add(k * 2 + 1, mid + 1, r, p, q, x);
        s[k] = max(s[k * 2], s[k * 2 + 1]);
    } void _modify(int k, int l, int r, int p, int q, tp x) {
        if (r < p || l > q) return;
        if (l >= p && r <= q) { _addmre(k, x); return; }
        _pushdown(k); _modify(k * 2, l, mid, p, q, x), _modify(k * 2 + 1, mid + 1, r, p, q, x);
        s[k] = max(s[k * 2], s[k * 2 + 1]);
    } tp _query(int k, int l, int r, int p, int q) {
        if (l >= p && r <= q) return s[k];
        _pushdown(k);
        if (mid < p) return _query(k * 2 + 1, mid + 1, r, p, q);
        if (mid >= q) return _query(k * 2, l, mid, p, q);
        return max(_query(k * 2 + 1, mid + 1, r, p, q), _query(k * 2, l, mid, p, q));
    }
public:
    void build(vp &a) {
        n = (int)a.size() - 1, s = mad = mre = vp(3 * n, -INIT), _build(1, 1, n, a);
    } void add(int l, int r, tp x) {
        _add(1, 1, n, l, r, x);
    } void modify(int l, int r, tp x) {
        _modify(1, 1, n, l, r, x);
    } tp query(int l, int r) {
        return _query(1, 1, n, l, r);
    }
#undef mid
#undef vp
};

标签：ll,return,入门,int,线段,mid,query,数据结构,void
From： https://www.cnblogs.com/RainPPR/p/17974548/segment-tree-2

相关文章

  • 若依框架入门一源码分析一登录验证码
    若依框架入门一源码分析一关于登录页面的验证码问题前端页面的验证码开关设置的是true，但是打开画面验证码没有被显示，原因是后端代码判断了redis中是否有值，有则覆盖前端<el-form-itemprop="code"v-if="captchaEnabled"><el-inputv-model="loginForm......
  • PostgreSQL从入门到精通教程 - 第42讲：pg_rman部署与使用
       PostgreSQL从小白到专家，是从入门逐渐能力提升的一个系列教程，内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容，希望对热爱PG、学习PG的同学们有帮助，欢迎持续关注CUUGPG技术大讲堂。 第42讲：pg_rman部署与使用 PostgreSQL第42讲：1月20日......
  • 二叉树 - 二叉树入门题
    二叉树入门题1.判断两颗树是否相同classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//如何判断两颗树是否相同?根相同+左右子树相同//如何判断根相同?结构+值相同if(p==null&&q!=null||p!=null&&......
  • 这才是你应该了解的Redis数据结构！
    深入了解Redis数据结构Redis，作为一种高性能的内存数据库，支持多种数据结构，从简单的字符串到复杂的哈希表。在这篇博文中，我们将深入探讨Redis的一些主要数据结构，并通过详细的例子展示它们的使用。1.字符串(String)1.1存储和获取Redis中的字符串是二进制安全的，可以存储任何数......
  • Python编程语法零基础入门
    0.开始前了解#号是一行注释"""6个"是多行注释"""#--coding:UTF-8print(u"你好!")#中文加上u转为unicode显示，不然会显示乱码1.基础语法和概念#(1)基本数据结构（整型、浮点型、字符串、布尔型）#格式：name=value没有分号、编译器自动匹配类型int_num=10float_num=......
  • kafka入门(八)：副本
    副本kafka副本之间是一主多从的关系。其中leader副本负责处理读写请求，follower副本只负责与leader副本的消息同步。副本处于不同的broker中，当leader副本出现故障时，从follower副本中重新选举新的leader副本对外提供服务。kafka通过多副本机制实现了故障的自动转......
  • 普普通通入门js案例(原生)
    数组中数据的遍历 vararr=[34,3,4,3]; for(i=0;i<arr.length;i++){ console.log(arr[i]); }求数组中的最大值 vararr=[34,3,4,3]; max=arr[0]; for(i=1;i<arr.length;i++){ if(max<arr[i]){ max=arr[i]; } }求数组中的平......
  • mysql8.0索引数据结构
    1、为什么使用索引假如给数据使用二叉树这样的数据结构进行存储，如下图所示2、索引及其优缺点2.1、索引概述2.2、优点（1）类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本，这也是创建索引最主要的原因。（2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性......
  • day 02java入门之Hello.java
    java命令行执行（注意代码编写用GBK，命令行窗口用GBK进行解析）注意public类名要和文件名一致,一个.java文件中最多只有一个public类java注意事项一个.java文件中若含有多个类时，编译完成后会生成相应个数的.class文件......
  • 跨语言调用神器SWIG介绍与使用入门
    安装依赖PCRE库apt-getinstalllibpcre2-dev下载安装$./configure$make$makeinstall介绍SWIG是一个软件开发工具，能够简化不同编程语言与C和C++程序连接的开发任务。简而言之，SWIG是一款编译器，它可以获取C/C++声明并创建访问这些声明所需的包装器，从而可从......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99