当前位置： 首页 > news >正文

浅谈线段树

news 来源：原创 2025/5/16 0:12:43

文章同步发布于洛谷，建议前往洛谷查看。

前言

蒟蒻终于学会线段树（指【模板】线段树 1 1 1）啦！

线段树思想

我们先来考虑 P3372（基础线段树模板题）给的操作：

  1. 区间修改（增加）
  2. 区间查询（求和）

很重要的一点是，两者是交叉的，要不然可以使用好写时间复杂度又优秀又好吃的前缀和秒了。

O ( 1 ) \mathcal O(1) O(1) 是困难的，所以我们思考可不可以 O ( log ⁡ n ) \bm{\mathcal O(\log n)} O(logn) 实现。

分段

目标

我们可以把一个区间分割成 O ( log ⁡ n ) \bm{\mathcal O(\log n)} O(logn) 个小区间（这一点非常重要），如果每个区间都可以 Θ ( 1 ) \bm{\Theta(1)} Θ(1) 完成（当然也很重要，但是如果是均摊 Θ ( 1 ) \Theta(1) Θ(1) 也行），则总时间复杂度为 O ( log ⁡ n ) \mathcal O(\log n) O(logn)。

较为失败的分段

我们的第一反应是把整个序列分割成几块，但是这样显然是不行的，哪里没割我们就可以把区间的一个端点设置为那个点，然后就无法分割了。如果把整个区间分割成每一个长度都是 1 1 1，则和数组无异，分割成的块数是 O ( n ) \bm{\mathcal O(n)} O(n) 的。

看起来不太有希望，但是我们可以换种思路。

线段树思想

一个位置可以被多个区间包含，而分割的方法是类似二进制。

这样做的好处：一个数字 k \bm k k 有 Θ ( log ⁡ k ) \bm{\Theta(\log k)} Θ(logk) 个二进制位，完美符合我们“一个序列被分割成 O ( log ⁡ k ) \mathcal O(\log k) O(logk) 个小序列”的要求。

这，就轮到线段树出场了。

这里插一句，为了发扬 STL 的传统美德，我们这里使用 [ a , b ) [a,b) [a,b) 左闭右开区间，同时下标从 0 0 0 开始。

我们假设序列长度是 2 k 2^k 2k：

  • 一个线段是 [ 0 , 2 k ) [0,2^k) [0,2k)
  • 一个线段是 [ 0 , 2 k − 1 ) [0,2^{k-1}) [0,2k−1)
  • 一个线段是 [ 2 k − 1 , 2 × 2 k − 1 ) [2^{k-1},2 \times 2^{k-1}) [2k−1,2×2k−1)
  • 一个线段是 [ 0 , 2 k − 2 ) [0,2^{k-2}) [0,2k−2)
  • 一个线段是 [ 2 k − 2 , 2 × 2 k − 2 ) [2^{k-2},2 \times 2^{k-2}) [2k−2,2×2k−2)
  • 一个线段是 [ 2 k − 1 , 3 × 2 k − 2 ) [2^{k-1},3 \times 2^{k-2}) [2k−1,3×2k−2)
  • 一个线段是 [ 3 × 2 k − 2 , 4 × 2 k − 2 ) [3 \times 2^{k-2}, 4 \times 2^{k-2}) [3×2k−2,4×2k−2)
  • …

我们把它以树的形式组织起来：

  • [ 0 , 2 k ) [0,2^k) [0,2k)
    • [ 0 , 2 k − 1 ) [0,2^{k-1}) [0,2k−1)
      • [ 0 , 2 k − 2 ) [0,2^{k-2}) [0,2k−2)
        • …
        • …
      • [ 2 k − 2 , 2 × 2 k − 2 ) [2^{k-2},2 \times 2^{k-2}) [2k−2,2×2k−2)
        • …
        • …
    • [ 2 k − 1 , 2 × 2 k − 1 ) [2^{k-1},2 \times 2^{k-1}) [2k−1,2×2k−1)
      • [ 2 k − 1 , 3 × 2 k − 2 ) [2^{k-1},3 \times 2^{k-2}) [2k−1,3×2k−2)
        • …
        • …
      • [ 3 × 2 k − 2 , 4 × 2 k − 2 ) [3 \times 2^{k-2}, 4 \times 2^{k-2}) [3×2k−2,4×2k−2)
        • …
        • …

或者，使用 Graph Editor？为了不让文字太长，这里令 k = 3 k = 3 k=3。

)

空间复杂度 Θ ( k 2 k ) \Theta(k2^k) Θ(k2k)，若 n = 2 k n = 2^k n=2k 则为 Θ ( n log ⁡ n ) \Theta(n \log n) Θ(nlogn)，可以完美承受。

这里，我们每一个节点不仅记录 [ l , r ) [l,r) [l,r) 范围，还要记录一个东西：范围里所有数字的和，以下称作 S S S。

复杂度假了

假设整个区间为 [ 0 , 8 ) [0,8) [0,8)，我们要把 [ 3 , 6 ) [3,6) [3,6) 这个区间的所有数字加一，我们可以：

  • 把区间 [ 0 , 8 ) [0,8) [0,8) 的 S S S 加 3 3 3；
  • 把区间 [ 0 , 4 ) [0,4) [0,4) 的 S S S 加 1 1 1；
  • 把区间 [ 2 , 4 ) [2,4) [2,4) 的 S S S 加 1 1 1；
  • 把区间 [ 3 , 4 ) [3,4) [3,4) 的 S S S 加 1 1 1；
  • 把区间 [ 4 , 8 ) [4,8) [4,8) 的 S S S 加 2 2 2；
  • 把区间 [ 4 , 6 ) [4,6) [4,6) 的 S S S 加 2 2 2；
  • 把区间 [ 4 , 5 ) [4,5) [4,5) 的 S S S 加 1 1 1；
  • 把区间 [ 5 , 6 ) [5,6) [5,6) 的 S S S 加 1 1 1。

看起来加了很多，复杂度真的是正确的吗？

很不幸，把区间内所有数字加上某个数字的时间复杂度为 Θ ( n log ⁡ n ) \bm{\Theta(n \log n)} Θ(nlogn)，还不如直接在数组上操作呢。

那么，这个思路就不行了吗？当然不是，我们刚才已经看到过这个思路的一次绝处逢生，为什么这一次就不行？

我们注意到，把 [ 4 , 6 ) [4,6) [4,6) 加 2 2 2 可以不涉及到原来的区间就推出后面的把 [ 4 , 5 ) [4,5) [4,5) 和 [ 5 , 6 ) [5,6) [5,6) 加一这两件事。

小 trick？

所以，我们有一个优化的小 trick（至于为什么要加双引号，待会儿就知道了）：在每次区间加的时候，如果是把整个区间加某个值，则先记录下来要加，并不把下面的整个子树都加上某一个值。

事实上，专门用来记录这个值的变量叫做 lazytag \text{lazytag} lazytag，以下为了节省 KaTeX \KaTeX KATE​X 的码量，则把它称作 tag \text{tag} tag（ KaTeX \KaTeX KATE​X 中 \text 内怎么加粗啊？/fn）

那么，加上这个 tag \text{tag} tag 之后，变成了什么样呢？

  • 把区间 [ 0 , 8 ) [0,8) [0,8) 的 S S S 加 3 3 3；
  • 把区间 [ 0 , 4 ) [0,4) [0,4) 的 S S S 加 1 1 1；
  • 把区间 [ 2 , 4 ) [2,4) [2,4) 的 S S S 加 1 1 1；
  • 把区间 [ 3 , 4 ) [3,4) [3,4) 的 S S S 加 1 1 1；
  • 把区间 [ 4 , 8 ) [4,8) [4,8) 的 S S S 加 2 2 2；
  • 把区间 [ 4 , 6 ) [4,6) [4,6) 的 S S S 加 2 2 2；
  • 把区间 [ 4 , 6 ) [4,6) [4,6) 的 tag \text{tag} tag 加 1 1 1。

看起来还是很多，但是我们惊喜的发现，如果在整个区间中都加上 v v v，我们只需要把 [ 0 , 8 ) [0,8) [0,8) 的 tag \text{tag} tag 加上 v v v 即可。

接下来进入 hack 模式。

hack！

hack 1 1 1：左边少一个元素

也就是 [ 1 , n ) [1,n) [1,n)。

分成两部分： [ 1 , n 2 ) [1,\frac{n}{2}) [1,2n​) 和 [ n 2 , n ) [\frac{n}{2},n) [2n​,n)，第二部分直接改一下 tag \text{tag} tag， Θ ( 1 ) \Theta(1) Θ(1) 处理掉了。

第一部分分成两部分： [ 1 , n 4 ) [1,\frac{n}{4}) [1,4n​) 和 [ n 4 , n 2 ) [\frac{n}{4},\frac{n}{2}) [4n​,2n​)，第二部分直接改一下 tag \text{tag} tag， Θ ( 1 ) \Theta(1) Θ(1) 处理掉了。

第一部分分成两部分： [ 1 , n 8 ) [1,\frac{n}{8}) [1,8n​) 和 [ n 8 , n 4 ) [\frac{n}{8},\frac{n}{4}) [8n​,4n​)，第二部分直接改一下 tag \text{tag} tag， Θ ( 1 ) \Theta(1) Θ(1) 处理掉了。

第一部分分成两部分： [ 1 , n 16 ) [1,\frac{n}{16}) [1,16n​) 和 [ n 16 , n 8 ) [\frac{n}{16},\frac{n}{8}) [16n​,8n​)，第二部分直接改一下 tag \text{tag} tag， Θ ( 1 ) \Theta(1) Θ(1) 处理掉了。

以此类推，时间复杂度： T ( n ) = T ( n 2 ) + Θ ( 1 ) T(n)=T(\frac{n}{2})+\Theta(1) T(n)=T(2n​)+Θ(1)，显然 T ( n ) = Θ ( log ⁡ n ) T(n)=\Theta(\log n) T(n)=Θ(logn)，也就是时间复杂度是 Θ ( log ⁡ n ) \bm{\Theta(\log n)} Θ(logn)。

完美接招。

hack 2 2 2：右边少一个元素

完美接招，把左边的稍微改改，变成每次第一部分直接 Θ ( 1 ) \Theta(1) Θ(1) 处理掉了，时间复杂度 Θ ( log ⁡ n ) \bm{\Theta(\log n)} Θ(logn)。

hack 3 3 3：左右边都少一个元素

本来以为可以成功 hack 的，但是分成两半之后我们发现：

左边：相当于 hack 1 1 1。

右边：相当于 hack 2 2 2。

然后 2 × Θ ( log ⁡ n ) = Θ ( log ⁡ n ) 2 \times \Theta(\log n) = \bm{\Theta(\log n)} 2×Θ(logn)=Θ(logn)，又是一次完美地应对。

如何查询

显然，只能修改还不行，还得查询。

查询也就不难了，按照相似的方式，在树上递归求解，遇到和原本序列完全一样的直接加。

时间复杂度？我们不乱 hack 了，直接求时间复杂度吧。

时间复杂度

首先感性理解一下，层数是 Θ ( log ⁡ n ) \Theta(\log n) Θ(logn) 的，所以时间复杂度是 O ( log ⁡ n ) \mathcal O(\log n) O(logn) 的。下面是严谨的证明，不想看可以跳过。

有几种情况：

  1. 序列和当前节点负责区间完全重合，直接返回，时间复杂度 Θ ( 1 ) \Theta(1) Θ(1)，不会继续递归。
  2. 序列左端点就是目前节点负责的区间左端点，右端点不到区间中点。此时递归可能会变成情况 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4。
  3. 序列左端点就是目前节点负责的区间左端点，右端点恰好为区间中点。此时递归可能会变成情况 1 1 1，也就是时间复杂度还是 Θ ( 1 ) \Theta(1) Θ(1)。
  4. 序列左端点就是目前节点负责的区间左端点，右端点超过区间中点。此时左边递归可能会变成情况 1 1 1，右边递归可能变成情况 2 , 3 , 4 2,3,4 2,3,4。
  5. 序列右端点就是目前节点负责的区间右端点，左端点不到区间中点。此时递归可能会变成情况 1 , 5 , 6 , 7 1,5,6,7 1,5,6,7。
  6. 序列右端点就是目前节点负责的区间右端点，左端点恰好为区间中点。此时递归可能会变成情况 1 1 1，也就是时间复杂度还是 Θ ( 1 ) \Theta(1) Θ(1)。
  7. 序列右端点就是目前节点负责的区间右端点，左端点超过区间中点。此时右边递归可能会变成情况 1 1 1，左边递归可能变成情况 5 , 6 , 7 5,6,7 5,6,7。
  8. 区间左端点和右端点都不是目前节点负责的左右端点，但是范围符合，左边可能递归成 5 , 6 , 7 5,6,7 5,6,7，右边可能是 2 , 3 , 4 2,3,4 2,3,4。
  9. 区间左端点和右端点都在左半部分，可能递归为 8 , 9 , 10 8,9,10 8,9,10
  10. 区间左端点和右端点都在右半部分，可能递归为 8 , 9 , 10 8,9,10 8,9,10

是不是看的有点晕？配合图片理解一下，黑色代表节点负责的区间，黑色中间的线代表中点，蓝色代表查询的点。

第一种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第二种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第三种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第四种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第五种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第六种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第七种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第八种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第九种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

第十种：外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

看个文章怎么跟个打音游一样

我们发现：只有第八种需要担心——有两个递归，可能导致时间复杂度变为 Θ ( n ) \Theta(n) Θ(n)。当然，第 9 9 9 和第 10 10 10 也需要担心，但是如果第 8 8 8 种解决了，这两种也就迎刃而解了。

我们发现，一旦经过一次第 8 8 8 中，就必然不会再经过第 8 , 9 8,9 8,9 或 10 10 10 种了。所以，如果我们把第 1 ∼ 7 1 \sim 7 1∼7 种和第 9 , 10 9,10 9,10 中当做两个组的话，那么 8 8 8 就是连接这两个组的桥梁。其中，第一个组花费的时间是 O ( log ⁡ n ) \mathcal O(\log n) O(logn) 的，第二个组也是，而“桥梁”最多被调用一次，所以最终时间复杂度是 O ( log ⁡ n ) + O ( log ⁡ n ) + 2 O ( log ⁡ n ) + O ( 1 ) = O ( log ⁡ n ) \mathcal O(\log n) + \mathcal O(\log n) + 2\mathcal O(\log n) + \mathcal O(1) = \bm{\mathcal O(\log n)} O(logn)+O(logn)+2O(logn)+O(1)=O(logn)。

查询时间复杂度也是 O ( log ⁡ n ) \bm{\mathcal O(\log n)} O(logn) 的。

修改时间复杂度

我们发现和查询几乎没有区别，原本时间复杂度假掉的原因只是第一种情况会变成和第八种一样的 T ( n ) = 2 T ( n 2 ) + Θ ( 1 ) T(n) = 2T(\frac{n}{2}) + \Theta(1) T(n)=2T(2n​)+Θ(1)，并且会变成两个第一种，时间复杂度直接废掉。加入 tag 之后就好啦！

时间复杂度证明和上述相同，是 O ( log ⁡ n ) \mathcal O(\log n) O(logn) 的。

这真的只是一个小 trick 吗？当然不是，这就是线段树的精髓，可以说，上面讲的思想就是线段树的灵魂，而这个 lazytag 就是线段树的骨架，缺一不可。

tag 的细节

在查询和修改时，如果一个标记已经有了 tag，那么这个 tag 可能会被使用，则需要把子树的标记加上本身的标记，然后修改 S S S，然后把标记清空，这一过程称作把标记下放（pushdown）。

代码

动态分配内存，然而静态开点。

// 需要 C++20 的 <bits> 头文件中的 bit_ceil 函数，作用是找到最小的 >= x 的 2 的幂，如果没有 C++20 也可以手写。// 线段/区间
template<typename T>
class segment
{
public:T l, r; // [l, r)size_t size() { return r - l; } // 长度bool fail() { return l >= r; } // 是否不合规template<typename Han_Si_Ying>friend bool operator==(const segment<Han_Si_Ying>& x, const segment<Han_Si_Ying>& y) { return x.l == y.l && x.r == y.r; } // Han_Si_Ying：？
};// 区间交
template<typename T>
segment<T> seg_and(segment<T> l1, segment<T> l2)
{return { max(l1.l, l2.l), min(l1.r, l2.r) };
}template<typename _Valt>
class segtree
{class segnode{public:segment<size_t> seg; // 负责区间_Valt s, tag; // S, lazytagsegnode* lp = nullptr, * rp = nullptr; // 左右子树void pushdown() // 下放标记{s += tag * seg.size();if (lp) lp->tag += tag;if (rp) rp->tag += tag;tag = 0;}};segnode* rt;void init(segnode* root, size_t l, size_t r) // 初始化{root->seg = { l,r };root->s = root->tag = _Valt();if (l + 1 == r) return;else{init(root->lp = new segnode, l, (l + r) >> 1);init(root->rp = new segnode, (l + r) >> 1, r);}}_Valt inn_query(segnode* root, segment<size_t> seg) // 区间查询{root->pushdown(); // 下放懒标记if (root->seg == seg) return root->s;segment<size_t> segl = seg_and(root->lp->seg, seg), segr = seg_and(root->rp->seg, seg); // 区间交_Valt sum = 0; // 和if (!segl.fail()) sum += inn_query(root->lp, segl);if (!segr.fail()) sum += inn_query(root->rp, segr);return sum;}void inn_add(segnode* root, segment<size_t> seg, _Valt val) // 区间修改{root->pushdown();if (root->seg == seg){root->tag += val;return;}root->s += val * seg.size();segment<size_t> segl = seg_and(root->lp->seg, seg),segr = seg_and(root->rp->seg, seg);if (!segr.fail()) inn_add(root->rp, segr, val);if (!segl.fail()) inn_add(root->lp, segl, val);}
public:segtree(size_t sz){sz = bit_ceil(sz); // 需要 2 的幂rt = new segnode{ 0, sz };init(rt, 0, sz);}_Valt query(size_t l, size_t r){return inn_query(rt, { l, r + 1 });}void add(size_t l, size_t r, _Valt x){inn_add(rt, { l, r + 1 }, x);}
};

相关文章：

浅谈线段树

文章同步发布于洛谷&#xff0c;建议前往洛谷查看。 前言 蒟蒻终于学会线段树&#xff08;指【模板】线段树 1 1 1&#xff09;啦&#xff01; 线段树思想 我们先来考虑 P3372&#xff08;基础线段树模板题&#xff09;给的操作&#xff1a; 区间修改&#xff08;增加&am…...

编程日记 2025/5/16 0:12:43

深度解读 Docker Swarm

一、引言 随着业务规模的不断扩大和应用复杂度的增加，容器集群管理的需求应运而生。如何有效地管理和调度大量的容器，确保应用的高可用性、弹性伸缩和资源的合理分配，成为了亟待解决的问题。Docker Swarm 作为 Docker 官方推出的容器集群管理工具，正是在这样的背景下崭露头…...

编程日记 2025/5/13 10:02:04

在线知识库的构建策略提升组织信息管理效率与决策能力

内容概要 在线知识库作为现代企业信息管理的重要组成部分&#xff0c;具有显著的定义与重要性。它不仅为组织提供了一个集中存储与管理知识的平台&#xff0c;还能够有效提升信息检索的效率&#xff0c;促进知识的创新和利用。通过这样的知识库&#xff0c;企业可以更好地应对…...

编程日记 2025/5/15 13:20:05

网件r7000刷回原厂固件合集测评

《网件R7000路由器刷回原厂固件详解》 网件R7000是一款备受赞誉的高性能无线路由器&#xff0c;其强大的性能和可定制性吸引了许多高级用户。然而&#xff0c;有时候用户可能会尝试第三方固件以提升功能或优化网络性能&#xff0c;但这也可能导致一些问题&#xff0c;如系统不…...

编程日记 2025/5/12 14:47:06

为什么命令“echo -e “\033[9；0]“ ＞ /dev/tty0“能控制开发板上的LCD不熄屏？

为什么命令"echo -e “\033[9;0]” > /dev/tty0"能控制开发板上的LCD不熄屏&#xff1f; 在回答这个问题前请先阅读我之前写的与tty和终端有关的博文 https://blog.csdn.net/wenhao_ir/article/details/145431655 然后再来看这条命令的解释就要容易些了。 这条…...

编程日记 2025/5/11 18:20:17

vscode软件操作界面UI布局@各个功能区域划分及其名称称呼

文章目录 abstract检查用户界面的主要区域官方文档关于UI的介绍 abstract 检查 Visual Studio Code 用户界面 - Training | Microsoft Learn 本质上&#xff0c;Visual Studio Code 是一个代码编辑器&#xff0c;其用户界面和布局与许多其他代码编辑器相似。 界面左侧是用于访…...

编程日记 2025/5/14 21:55:50

【Java基础-42.3】Java 基本数据类型与字符串之间的转换：深入理解数据类型的转换方法

在 Java 开发中&#xff0c;基本数据类型与字符串之间的转换是非常常见的操作。无论是从用户输入中读取数据&#xff0c;还是将数据输出到日志或界面&#xff0c;都需要进行数据类型与字符串之间的转换。本文将深入探讨 Java 中基本数据类型与字符串之间的转换方法&#xff0c;…...

编程日记 2025/5/13 1:48:08

【ActiveMq RocketMq RabbitMq Kafka对比】

以下是 ActiveMQ、RocketMQ、RabbitMQ 和 Kafka 的对比表格&#xff0c;从复杂性、功能、性能和适用场景等方面进行整理&#xff1a; 特性ActiveMQRocketMQRabbitMQKafka开发语言JavaJavaErlangScala/Java协议支持AMQP、STOMP、MQTT、OpenWire 等自定义协议AMQP、STOMP、MQTT …...

编程日记 2025/5/7 6:28:46

csapp笔记3.6节——控制（1）

本节解决了x86-64如何实现条件语句、循环语句和分支语句的问题 条件码 除了整数寄存器外&#xff0c;cpu还维护着一组单个位的条件码寄存器&#xff0c;用来描述最近的算数和逻辑运算的某些属性。可检测这些寄存器来执行条件分支指令。 CF&#xff08;Carry Flag&#xff09…...

编程日记 2025/5/14 21:46:26

网站快速收录：如何优化网站音频内容？

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/60.html 为了优化网站音频内容以实现快速收录&#xff0c;以下是一些关键的策略和步骤&#xff1a; 一、高质量音频内容创作 原创性&#xff1a; 确保音频内容是原创的&#xff0c;避免使…...

编程日记 2025/5/12 14:17:58

音视频入门基础：RTP专题（8）——使用Wireshark分析RTP

一、引言 通过Wireshark可以抓取RTP数据包&#xff0c;该软件可以从Wireshark Go Deep 下载。 二、通过Wireshark抓取RTP数据包 首先通过FFmpeg将一个媒体文件转推RTP&#xff0c;生成RTP流&#xff1a; ffmpeg -re -stream_loop -1 -i input.mp4 -vcodec copy -an -f rtp …...

编程日记 2025/5/14 11:02:20

4-图像梯度计算

文章目录 4.图像梯度计算（1）Sobel算子（2）梯度计算方法（3）Scharr与Laplacian算子4.图像梯度计算 （1）Sobel算子 图像梯度-Sobel算子 Sobel算子是一种经典的图像边缘检测算子，广泛应用于图像处理和计算机视觉领域。以下是关于Sobel算子的详细介绍： 基本原理 Sobel算子…...

编程日记 2025/5/12 11:15:39

深入解析 Redis AOF 机制：持久化原理、重写优化与 COW 影响

深入解析 Redis AOF 机制&#xff1a;持久化原理、重写优化与 COW 影响 1. 引言2. AOF 机制详解2.1 AOF 解决了什么问题&#xff1f;2.2 AOF 写入机制2.2.1 AOF 的基本原理2.2.2 AOF 运行流程2.2.3 AOF 文件刷盘策略 3. AOF 重写机制3.1 AOF 文件为什么会变大&#xff1f;3.2 解…...

编程日记 2025/5/14 14:31:46

机器学习day8

自定义数据集 &#xff0c;使用朴素贝叶斯对其进行分类 代码 import numpy as np import matplotlib.pyplot as pltclass1_points np.array([[2.1, 2.2], [2.4, 2.5], [2.2, 2.0], [2.0, 2.1], [2.3, 2.3], [2.6, 2.4], [2.5, 2.1]]) class2_points np.array([[4.0, 3.5], …...

编程日记 2025/5/13 5:25:28

【前端】ES6模块化

文章目录 1. 模块化概述1.1 什么是模块化?1.2 为什么需要模块化? 2. 有哪些模块化规范3. CommonJs3.1 导出数据3.2 导入数据3.3 扩展理解3.4 在浏览器端运行 4.ES6模块化 参考视频地址 1. 模块化概述 1.1 什么是模块化? 将程序文件依据一定规则拆分成多个文件,这种编码方式…...

编程日记 2025/5/15 17:49:52

【leetcode练习·二叉树拓展】快速排序详解及应用

本文参考labuladong算法笔记[拓展&#xff1a;快速排序详解及应用 | labuladong 的算法笔记] 1、算法思路 首先我们看一下快速排序的代码框架&#xff1a; def sort(nums: List[int], lo: int, hi: int):if lo > hi:return# 对 nums[lo..hi] 进行切分# 使得 nums[lo..p-1]…...

编程日记 2025/5/11 17:37:27

Gurobi基础语法之 addConstr, addConstrs, addQConstr, addMQConstr

在新版本的 Gurobi 中&#xff0c;向 addConstr 这个方法中传入一个 TempConstr 对象&#xff0c;在模型中就会根据这个对象生成一个约束。更重要的是&#xff1a;TempConstr 对象可以传给所有addConstr系列方法&#xff0c;所以下面先介绍 TempConstr 对象 TempConstr TempC…...

编程日记 2025/5/15 4:00:50

游戏引擎 Unity - Unity 设置为简体中文、Unity 创建项目

Unity Unity 首次发布于 2005 年&#xff0c;属于 Unity Technologies Unity 使用的开发技术有&#xff1a;C# Unity 的适用平台&#xff1a;PC、主机、移动设备、VR / AR、Web 等 Unity 的适用领域&#xff1a;开发中等画质中小型项目 Unity 适合初学者或需要快速上手的开…...

编程日记 2025/5/13 3:18:49

Kamailio、MySQL、Redis、Gin后端、Vue.js前端等基于容器化部署

基于容器化的部署方案&#xff0c;通常会将每个核心服务&#xff08;如Kamailio、MySQL、Redis、Gin后端、Vue.js前端等&#xff09;独立运行在不同的容器中&#xff0c;通过Docker或Kubernetes统一管理。以下是具体实现方式和关键原因&#xff1a; 1. 容器化部署的核心思路 每…...

编程日记 2025/5/15 10:59:15

从1号点到n号点最多经过k条边的最短距离

目录 解析方法思路代码解释代码逐行注释1. 头文件和常量定义&#xff1a;2.边的结构体&#xff1a;3.全局变量&#xff1a;4.Bellman-Ford算法实现&#xff1a;5.主函数&#xff1a; 注意事项代码含义为什么需要 backup[a]&#xff1f;举例说明关键点 总结 解析 要实现从1号点…...

编程日记 2025/5/16 6:36:58

模拟实战-用CompletableFuture优化远程RPC调用

实战场景 这是广州某500-900人互联网厂的面试原题 手写并发优化解决思路 我们要调用对方的RPC接口&#xff0c;我们的RPC接口每调用一次对方都会阻塞50ms 但是我们的业务要批量调用RPC&#xff0c;例如我们要批量调用1k次&#xff0c;我们不可能在for循环里面写1k次远程调用…...

编程日记 2025/5/12 15:18:43

【pinia状态管理配置】

pinia状态管理配置 安装main.ts引入自定义user仓库使用自定义仓库 安装 pnpm add piniamain.ts引入 // createPinia() 函数调用创建了一个新的 Pinia 实例。 // 这个实例是状态管理的核心&#xff0c;它将管理应用中所有的 store。 import { createPinia } from pinia app.us…...

编程日记 2025/5/16 7:13:44

SpringBoot 引⼊MybatisGenerator

SpringBoot 引⼊MybatisGenerator 1. 引入插件2. 添加generator.xml并修改3. 生成文件 1. 引入插件 <plugin><groupId>org.mybatis.generator</groupId><artifactId>mybatis-generator-maven-plugin</artifactId><version>1.3.5</vers…...

编程日记 2025/5/16 7:08:04

在线销售数据集分析：基于Python的RFM数据分析方法实操训练

一、前言 个人练习&#xff0c;文章用于记录自己的学习练习过程&#xff0c;分享出来和大家一起学习。 数据集&#xff1a;在线销售数据集 分析方法&#xff1a;RFM分析方法 二、过程 1.1 库的导入与一些必要的初始设置 import pandas as pd import datetime import matplo…...

编程日记 2025/5/16 7:10:19

LeetCode - #197 Swift 实现找出温度更高的日期

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/5/16 6:56:33

分析哲学：从 语言解剖到 思想澄清的哲学探险

分析哲学&#xff1a;从 语言解剖 到 思想澄清 的哲学探险 第一节&#xff1a;分析哲学的基本概念与公式解释 【通俗讲解&#xff0c;打比方来讲解&#xff01;】 分析哲学&#xff0c;就像一位 “语言侦探”&#xff0c;专注于 “解剖语言”&#xff0c;揭示我们日常使用的语…...

编程日记 2025/5/16 2:17:10

C++【iostream】数据库的部分函数功能介绍

在 C 编程世界中&#xff0c;iostream 库扮演着举足轻重的角色&#xff0c;它是 C 标准库的核心组成部分&#xff0c;为程序提供了强大的输入输出功能。无论是简单的控制台交互&#xff0c;还是复杂的文件操作&#xff0c;iostream 库都能提供便捷高效的解决方案。本文将深入剖…...

编程日记 2025/5/15 13:48:14

金山打字游戏2010绿色版，Win7-11可用DxWnd完美运行

金山打字游戏2010绿色版&#xff0c;Win7-11可用DxWnd完美运行 链接&#xff1a;https://pan.xunlei.com/s/VOIAYCzmkbDfdASGJa_uLjquA1?pwd67vw# 进入游戏后&#xff0c;如果输入不了英文字母&#xff08;很可能是中文输入状态&#xff09;&#xff0c;就按一下“Shift”键…...

编程日记 2025/5/12 2:46:13

洛谷[USACO08DEC] Patting Heads S

题目传送门 题目难度&#xff1a;普及/提高一 题面翻译 今天是贝茜的生日&#xff0c;为了庆祝自己的生日&#xff0c;贝茜邀你来玩一个游戏。 贝茜让 N N N ( 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1≤N≤105) 头奶牛坐成一个圈。除了 1 1 1 号与 N N N 号奶牛外&#xff0…...

编程日记 2025/5/16 6:25:26

讲清逻辑回归算法，剖析其作为广义线性模型的原因

1、逻辑回归算法介绍 逻辑回归(Logistic Regression)是一种广义线性回归分析模型。虽然名字里带有“回归”两字&#xff0c;但其实是分类模型&#xff0c;常用于二分类。既然逻辑回归模型是分类模型&#xff0c;为什么名字里会含有“回归”二字呢&#xff1f;这是因为其算法原…...

编程日记 2025/5/16 7:01:26

基于STM32的智能安防监控系统

1. 引言 随着物联网技术的普及&#xff0c;智能安防系统在家庭与工业场景中的应用日益广泛。本文设计了一款基于STM32的智能安防监控系统&#xff0c;集成人体感应、环境异常检测、图像识别与云端联动功能&#xff0c;支持实时报警、远程监控与数据回溯。该系统采用边缘计算与…...

编程日记 2025/5/15 22:31:41

八. Spring Boot2 整合连接 Redis(超详细剖析)

八. Spring Boot2 整合连接 Redis(超详细剖析) 文章目录 八. Spring Boot2 整合连接 Redis(超详细剖析)2. 注意事项和细节3. 最后&#xff1a; 在 springboot 中 , 整合 redis 可以通过 RedisTemplate 完成对 redis 的操作, 包括设置数据/获取数据 比如添加和读取数据 具体整…...

编程日记 2025/5/13 5:03:38

220.存在重复元素③

目录 一、题目二、思路三、解法四、收获 一、题目 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。 找出满足下述条件的下标对 (i, j)&#xff1a; i ! j, abs(i - j) < indexDiff abs(nums[i] - nums[j]) < valueDiff 如果存在&#xff0c;返回 true &a…...

编程日记 2025/5/16 7:41:31

【Linux】从硬件到软件了解进程

个人主页~ 从硬件到软件了解进程 一、冯诺依曼体系结构二、操作系统三、操作系统进程管理1、概念2、PCB和task_struct3、查看进程4、通过系统调用fork创建进程&#xff08;1&#xff09;简述&#xff08;2&#xff09;系统调用生成子进程的过程〇提出问题①fork函数②父子进程关…...

编程日记 2025/5/16 7:10:19

volatile变量需要减少读取次数吗

问题说明 本人在前期读Netty源码时看到这样一段源码和注释&#xff1a; private boolean invokeHandler() {// Store in local variable to reduce volatile reads.int handlerState this.handlerState;return handlerState ADD_COMPLETE || (!ordered && handlerS…...

编程日记 2025/5/16 7:15:07

红黑树的封装

一、封装思路 在 STL 中 map set 的底层就是封装了一棵红黑树。 其中连接红黑树和容器的是迭代器&#xff0c;map set 暴露出的接口都不是自己写的&#xff0c;而是红黑树写的&#xff0c;外部接口封装红黑树接口。 所以写出红黑树为 map set 写的接口&#xff0c;再在上层的…...

编程日记 2025/5/16 7:11:32

Java 泛型＜? extends Object＞

在 Java 泛型中&#xff0c;<? extends Object> 和 <?> 都表示未知类型&#xff0c;但它们在某些情况下有细微的差异。泛型的引入是为了消除运行时错误并增强类型安全性&#xff0c;使代码更具可读性和可维护性。 在 JDK 5 中引入了泛型&#xff0c;以消除编译时…...

编程日记 2025/5/15 4:23:34

TensorFlow简单的线性回归任务

如何使用 TensorFlow 和 Keras 创建、训练并进行预测 1. 数据准备与预处理 2. 构建模型 3. 编译模型 4. 训练模型 5. 评估模型 6. 模型应用与预测 7. 保存与加载模型 8.完整代码 1. 数据准备与预处理 我们将使用一个简单的线性回归问题&#xff0c;其中输入特征 x 和标…...

编程日记 2025/5/16 7:09:12

解码大数据的四个V：体积、速度、种类与真实性

解码大数据的四个V&#xff1a;体积、速度、种类与真实性 在大数据领域&#xff0c;有一个大家耳熟能详的概念——“四个V”&#xff1a;Volume&#xff08;体积&#xff09;、Velocity&#xff08;速度&#xff09;、Variety&#xff08;种类&#xff09;、Veracity&#xff…...

编程日记 2025/5/14 13:20:24

【单层神经网络】基于MXNet的线性回归实现（底层实现）

写在前面 基于亚马逊的MXNet库本专栏是对李沐博士的《动手学深度学习》的笔记&#xff0c;仅用于分享个人学习思考以下是本专栏所需的环境&#xff08;放进一个environment.yml&#xff0c;然后用conda虚拟环境统一配置即可&#xff09;刚开始先从普通的寻优算法开始&#xff…...

编程日记 2025/5/15 12:16:41

深入解析 posix_spawn()：高效的进程创建方式（中英双语）

深入解析 posix_spawn()&#xff1a;高效的进程创建方式 1. 引言 在 Unix/Linux 系统中&#xff0c;传统的进程创建方式主要依赖 fork() 和 exec() 组合。但 fork() 在某些情况下可能存在性能瓶颈&#xff0c;特别是当父进程占用大量内存时&#xff0c;fork() 仍然需要复制整…...

编程日记 2025/5/16 2:33:29

2024-我的学习成长之路

因为热爱&#xff0c;无畏山海...

编程日记 2025/5/15 8:20:13

【Java异步编程】基于任务类型创建不同的线程池

文章目录 一. 按照任务类型对线程池进行分类1. IO密集型任务的线程数2. CPU密集型任务的线程数3. 混合型任务的线程数 二. 线程数越多越好吗三. Redis 单线程的高效性 使用线程池的好处主要有以下三点&#xff1a; 降低资源消耗&#xff1a;线程是稀缺资源&#xff0c;如果无限…...

编程日记 2025/5/15 8:36:13

前缀和多种基础

前缀和加法 #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int n; const int N 1e310; int arr[N]; int pre[N]; int org[N]; int main(void) {cin >> n;for(int i 1 ; i < n ; i){cin >> arr[i];pre[i] …...

编程日记 2025/5/15 3:12:09

关于贪心学习的文笔记录

贪心&#xff0c;顾名思义就是越贪越好&#xff0c;越多越有易&#xff0c;他给我的感觉是&#xff0c;通常是求最大或最小问题&#xff0c;相比于动态规划贪心让人更加琢磨不透&#xff0c;不易看出方法&#xff0c;为此在这记录我所见过的题型和思维方法&#xff0c;以便回头…...

编程日记 2025/5/15 12:46:57

蓝桥杯思维训练营(三）

文章目录 题目详解680.验证回文串 II30.魔塔游戏徒步旅行中的补给问题观光景点组合得分问题 题目详解 680.验证回文串 II 680.验证回文串 II 思路分析&#xff1a;这个题目的关键就是&#xff0c;按照正常来判断对应位置是否相等&#xff0c;如果不相等&#xff0c;那么就判…...

编程日记 2025/5/11 21:19:01

农历2025开始 笔记

2/3 Hey everyone! The Chinese New Year holiday is over. I spent over ten days back home, and honestly, I feel even more exhausted than when I’m working. Yesterday, I drove for 13 hours straight and finally made it back. In a couple of days, I’ll officia…...

编程日记 2025/5/15 14:05:07

VR触感数据手套：触感反馈赋予虚拟交互沉浸式体验

随着动作捕捉技术的蓬勃发展&#xff0c;动捕数据手套成为了手部动作捕捉与虚拟交互的便捷工具&#xff0c;为人们打开了通往虚拟世界的新大门。在众多产品中&#xff0c;mHand Pro作为一款多功能兼具的VR动作捕捉数据手套&#xff0c;凭借其卓越的性能&#xff0c;在手部动作捕…...

编程日记 2025/5/15 11:13:50

6 [新一代Github投毒针对网络安全人员钓鱼]

0x01 前言 在Github上APT组织“海莲花”发布存在后门的提权BOF&#xff0c;通过该项目针对网络安全从业人员进行钓鱼。不过其实早在几年前就已经有人对Visual Studio项目恶意利用进行过研究&#xff0c;所以投毒的手法也不算是新的技术。但这次国内有大量的安全从业者转发该钓…...

编程日记 2025/5/12 11:19:29

基于LabVIEW的Modbus-RTU设备通信失败问题分析与解决

在使用 LabVIEW 通过 Modbus-RTU 协议与工业设备进行通信时&#xff0c;可能遇到无法正常发送或接收指令的问题。常见原因包括协议参数配置错误、硬件连接问题、数据帧格式不正确等。本文以某 RGBW 控制器调光失败为例&#xff0c;提出了一种通用的排查思路&#xff0c;帮助开发…...

编程日记 2025/5/11 9:45:05