数据结构与算法专题——第七题线段树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法专题——第七题线段树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11948字，纯文字阅读大概需要18分钟。

内容图文

这一篇我们来看树状数组的加强版线段树，树状数组能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均等经典的RMQ问题上有着对数时间的优越表现。

一：线段树

线段树又称 "区间树”，在每个节点上保存一个区间，当然区间的划分采用折半的思想，叶子节点只保存一个值，也叫单元节点，所以最终的构造就是一个平衡的二叉树，拥有CURD的O(logN)的时间。

数据结构与算法专题——第七题线段树 - 文章图片

从图中我们可以清楚的看到 [0-10] 被划分成线段在树中的分布情况，针对区间 [0-N]，最多有 2N 个节点，由于是平衡二叉树的形式也可以像堆那样用数组来玩，不过更加耗费空间，为最多4N个节点，在针对RMQ的问题上，你可以在每个节点上增加一些sum，max，min等变量来记录求得的累加值，当然你也可以理解成动态规划的思想，由于拥有logN的时间，所以在RMQ问题上比数组更加优美。

二：代码

1: 在节点中定义一些附加值，方便我们处理RMQ问题。


 ? ? ? ?/// <summary>
 ? ? ? ?/// 线段树的节点
 ? ? ? ?/// </summary>
 ? ? ? ?public class Node
 ? ? ? ?{
 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 区间左端点
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int left;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 区间右端点
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int right;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 左孩子
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public Node leftchild;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 右孩子
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public Node rightchild;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的sum值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Sum;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的Min值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Min;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的Max值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Max;
 ? ? ? ?}

2：构建(Build)

通常构建的方式有两种，要么数组要么链式，各有特点，我就采用后者，时间为O(N)。


 ? ? ? ?/// <summary>
 ? ? ? ?/// 根据数组构建“线段树"
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="length"></param>
 ? ? ? ?public Node Build(int[] nums)
 ? ? ? ?{
 ? ? ? ? ? ?this.nums = nums;

 ? ? ? ? ? ?return Build(nodeTree, 0, nums.Length - 1);
 ? ? ? ?}

 ? ? ? ?/// <summary>
 ? ? ? ?/// 根据数组构建“线段树"
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="left"></param>
 ? ? ? ?/// <param name="right"></param>
 ? ? ? ?public Node Build(Node node, int left, int right)
 ? ? ? ?{
 ? ? ? ? ? ?//说明已经到根了，当前当前节点的max，sum，min值（回溯时统计上一层节点区间的值）
 ? ? ? ? ? ?if (left == right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?return new Node
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?left = left,
 ? ? ? ? ? ? ? ? ? ?right = right,
 ? ? ? ? ? ? ? ? ? ?Max = nums[left],
 ? ? ? ? ? ? ? ? ? ?Min = nums[left],
 ? ? ? ? ? ? ? ? ? ?Sum = nums[left]
 ? ? ? ? ? ? ? ?};
 ? ? ? ? ? ?}

 ? ? ? ? ? ?if (node == null)
 ? ? ? ? ? ? ? ?node = new Node();

 ? ? ? ? ? ?node.left = left;

 ? ? ? ? ? ?node.right = right;

 ? ? ? ? ? ?node.leftchild = Build(node.leftchild, left, (left + right) / 2);

 ? ? ? ? ? ?node.rightchild = Build(node.rightchild, (left + right) / 2 + 1, right);

 ? ? ? ? ? ?//统计左右子树的值(min，max，sum)
 ? ? ? ? ? ?node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
 ? ? ? ? ? ?node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
 ? ? ? ? ? ?node.Sum = node.leftchild.Sum + node.rightchild.Sum;

 ? ? ? ? ? ?return node;
 ? ? ? ?}

3：区间查询

在线段树中，区间查询还是有点小麻烦的，存在三种情况。

① 完全包含：也就是节点的线段范围完全在查询区间的范围内，这说明我们要么到了“单元节点",要么到了一个子区间，这种情况就是我找到了查询区间的某一个子区间，直接累积该区间值就可以了。

② 左交集：这种情况我们需要到左子树去遍历。

③ 右交集：这种情况我们需要到右子树去遍历。

比如说：我要查询Sum[4-8]的值,最终会成为:Sum总=Sum[4-4]+Sum[5-5]+Sum[6-8]，时间为log(N)。


 ? ? ? ?/// <summary>
 ? ? ? ?/// 区间查询(分解)
 ? ? ? ?/// </summary>
 ? ? ? ?/// <returns></returns>
 ? ? ? ?public int Query(int left, int right)
 ? ? ? ?{
 ? ? ? ? ? ?int sum = 0;

 ? ? ? ? ? ?Query(nodeTree, left, right, ref sum);

 ? ? ? ? ? ?return sum;
 ? ? ? ?}

 ? ? ? ?/// <summary>
 ? ? ? ?/// 区间查询
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="left">查询左边界</param>
 ? ? ? ?/// <param name="right">查询右边界</param>
 ? ? ? ?/// <param name="node">查询的节点</param>
 ? ? ? ?/// <returns></returns>
 ? ? ? ?public void Query(Node node, int left, int right, ref int sum)
 ? ? ? ?{
 ? ? ? ? ? ?//说明当前节点完全包含在查询范围内，两点：要么是单元节点，要么是子区间
 ? ? ? ? ? ?if (left <= node.left && right >= node.right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//获取当前节点的sum值
 ? ? ? ? ? ? ? ?sum += node.Sum;
 ? ? ? ? ? ? ? ?return;
 ? ? ? ? ? ?}
 ? ? ? ? ? ?else
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//如果当前的left和right 和node的left和right无交集，此时可返回
 ? ? ? ? ? ? ? ?if (node.left > right || node.right < left)
 ? ? ? ? ? ? ? ? ? ?return;

 ? ? ? ? ? ? ? ?//找到中间线
 ? ? ? ? ? ? ? ?var middle = (node.left + node.right) / 2;

 ? ? ? ? ? ? ? ?//左孩子有交集
 ? ? ? ? ? ? ? ?if (left <= middle)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?Query(node.leftchild, left, right, ref sum);
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ? ? ?//右孩子有交集
 ? ? ? ? ? ? ? ?if (right >= middle)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?Query(node.rightchild, left, right, ref sum);
 ? ? ? ? ? ? ? ?}

 ? ? ? ? ? ?}
 ? ? ? ?}

4：更新操作

这个操作跟树状数组中的更新操作一样，当递归的找到待修改的节点后，改完其值然后在当前节点一路回溯，并且在回溯的过程中一路修改父节点的附加值直到根节点，至此我们的操作就完成了，复杂度同样为logN。


 ? ? ? ?/// <summary>
 ? ? ? ?/// 更新操作
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="index"></param>
 ? ? ? ?/// <param name="key"></param>
 ? ? ? ?public void Update(int index, int key)
 ? ? ? ?{
 ? ? ? ? ? ?Update(nodeTree, index, key);
 ? ? ? ?}

 ? ? ? ?/// <summary>
 ? ? ? ?/// 更新操作
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="index"></param>
 ? ? ? ?/// <param name="key"></param>
 ? ? ? ?public void Update(Node node, int index, int key)
 ? ? ? ?{
 ? ? ? ? ? ?if (node == null)
 ? ? ? ? ? ? ? ?return;

 ? ? ? ? ? ?//取中间值
 ? ? ? ? ? ?var middle = (node.left + node.right) / 2;

 ? ? ? ? ? ?//遍历左子树
 ? ? ? ? ? ?if (index >= node.left && index <= middle)
 ? ? ? ? ? ? ? ?Update(node.leftchild, index, key);

 ? ? ? ? ? ?//遍历右子树
 ? ? ? ? ? ?if (index <= node.right && index >= middle + 1)
 ? ? ? ? ? ? ? ?Update(node.rightchild, index, key);

 ? ? ? ? ? ?//在回溯的路上一路更改，复杂度为lgN
 ? ? ? ? ? ?if (index >= node.left && index <= node.right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//说明找到了节点
 ? ? ? ? ? ? ? ?if (node.left == node.right)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?nums[index] = key;

 ? ? ? ? ? ? ? ? ? ?node.Sum = node.Max = node.Min = key;
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?//回溯时统计左右子树的值(min，max，sum)
 ? ? ? ? ? ? ? ? ? ?node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
 ? ? ? ? ? ? ? ? ? ?node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
 ? ? ? ? ? ? ? ? ? ?node.Sum = node.leftchild.Sum + node.rightchild.Sum;
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ?}
 ? ? ? ?}

最后我们做个例子，在2000000的数组空间中，寻找200-3000区间段的sum值，看看他的表现如何。


 ? ?public class Program
 ? ?{
 ? ? ? ?public static void Main()
 ? ? ? ?{
 ? ? ? ? ? ?int[] nums = new int[200 * 10000];
 ? ? ? ? ? ?for (int i = 0; i < 10000 * 200; i++) nums[i] = i;
 ? ? ? ? ? ?Tree tree = new Tree();
 ? ? ? ? ? ?//将当前数组构建成 “线段树”
 ? ? ? ? ? ?tree.Build(nums);
 ? ? ? ? ? ?var watch = Stopwatch.StartNew();
 ? ? ? ? ? ?var sum = tree.Query(200, 3000);
 ? ? ? ? ? ?watch.Stop();
 ? ? ? ? ? ?Console.WriteLine("耗费时间:{0}ms, ?当前数组有:{1}个数字, 求出Sum=:{2}", watch.ElapsedMilliseconds, nums.Length, sum);
 ? ? ? ? ? ?Console.Read();
 ? ? ? ?}
 ? ?}

 ? ?public class Tree
 ? ?{
 ? ? ? ?public class Node
 ? ? ? ?{
 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 区间左端点
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int left;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 区间右端点
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int right;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 左孩子
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public Node leftchild;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 右孩子
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public Node rightchild;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的sum值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Sum;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的Min值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Min;

 ? ? ? ? ? ?/// <summary>
 ? ? ? ? ? ?/// 节点的Max值
 ? ? ? ? ? ?/// </summary>
 ? ? ? ? ? ?public int Max;
 ? ? ? ?}

 ? ? ? ?Node nodeTree = new Node();

 ? ? ? ?int[] nums;

 ? ? ? ?public Node Build(int[] nums)
 ? ? ? ?{
 ? ? ? ? ? ?this.nums = nums;
 ? ? ? ? ? ?return Build(nodeTree, 0, nums.Length - 1);
 ? ? ? ?}

 ? ? ? ?public Node Build(Node node, int left, int right)
 ? ? ? ?{
 ? ? ? ? ? ?//说明已经到根了，当前当前节点的max，sum，min值（回溯时统计上一层节点区间的值）
 ? ? ? ? ? ?if (left == right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?return new Node
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?left = left,
 ? ? ? ? ? ? ? ? ? ?right = right,
 ? ? ? ? ? ? ? ? ? ?Max = nums[left],
 ? ? ? ? ? ? ? ? ? ?Min = nums[left],
 ? ? ? ? ? ? ? ? ? ?Sum = nums[left]
 ? ? ? ? ? ? ? ?};
 ? ? ? ? ? ?}

 ? ? ? ? ? ?if (node == null)
 ? ? ? ? ? ? ? ?node = new Node();

 ? ? ? ? ? ?node.left = left;

 ? ? ? ? ? ?node.right = right;

 ? ? ? ? ? ?node.leftchild = Build(node.leftchild, left, (left + right) / 2);

 ? ? ? ? ? ?node.rightchild = Build(node.rightchild, (left + right) / 2 + 1, right);

 ? ? ? ? ? ?//统计左右子树的值(min，max，sum)
 ? ? ? ? ? ?node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
 ? ? ? ? ? ?node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
 ? ? ? ? ? ?node.Sum = node.leftchild.Sum + node.rightchild.Sum;

 ? ? ? ? ? ?return node;
 ? ? ? ?}

 ? ? ? ?public int Query(int left, int right)
 ? ? ? ?{
 ? ? ? ? ? ?int sum = 0;
 ? ? ? ? ? ?Query(nodeTree, left, right, ref sum);
 ? ? ? ? ? ?return sum;
 ? ? ? ?}

 ? ? ? ?public void Query(Node node, int left, int right, ref int sum)
 ? ? ? ?{
 ? ? ? ? ? ?//说明当前节点完全包含在查询范围内，两点：要么是单元节点，要么是子区间
 ? ? ? ? ? ?if (left <= node.left && right >= node.right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//获取当前节点的sum值
 ? ? ? ? ? ? ? ?sum += node.Sum;
 ? ? ? ? ? ? ? ?return;
 ? ? ? ? ? ?}
 ? ? ? ? ? ?else
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//如果当前的left和right 和node的left和right无交集，此时可返回
 ? ? ? ? ? ? ? ?if (node.left > right || node.right < left)
 ? ? ? ? ? ? ? ? ? ?return;

 ? ? ? ? ? ? ? ?//找到中间线
 ? ? ? ? ? ? ? ?var middle = (node.left + node.right) / 2;

 ? ? ? ? ? ? ? ?//左孩子有交集
 ? ? ? ? ? ? ? ?if (left <= middle)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?Query(node.leftchild, left, right, ref sum);
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ? ? ?//右孩子有交集
 ? ? ? ? ? ? ? ?if (right >= middle)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?Query(node.rightchild, left, right, ref sum);
 ? ? ? ? ? ? ? ?}

 ? ? ? ? ? ?}
 ? ? ? ?}

 ? ? ? ?public void Update(int index, int key)
 ? ? ? ?{
 ? ? ? ? ? ?Update(nodeTree, index, key);
 ? ? ? ?}

 ? ? ? ?/// <summary>
 ? ? ? ?/// 更新操作
 ? ? ? ?/// </summary>
 ? ? ? ?/// <param name="index"></param>
 ? ? ? ?/// <param name="key"></param>
 ? ? ? ?public void Update(Node node, int index, int key)
 ? ? ? ?{
 ? ? ? ? ? ?if (node == null)
 ? ? ? ? ? ? ? ?return;

 ? ? ? ? ? ?//取中间值
 ? ? ? ? ? ?var middle = (node.left + node.right) / 2;

 ? ? ? ? ? ?//遍历左子树
 ? ? ? ? ? ?if (index >= node.left && index <= middle)
 ? ? ? ? ? ? ? ?Update(node.leftchild, index, key);

 ? ? ? ? ? ?//遍历右子树
 ? ? ? ? ? ?if (index <= node.right && index >= middle + 1)
 ? ? ? ? ? ? ? ?Update(node.rightchild, index, key);

 ? ? ? ? ? ?//在回溯的路上一路更改，复杂度为lgN
 ? ? ? ? ? ?if (index >= node.left && index <= node.right)
 ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ?//说明找到了节点
 ? ? ? ? ? ? ? ?if (node.left == node.right)
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?nums[index] = key;

 ? ? ? ? ? ? ? ? ? ?node.Sum = node.Max = node.Min = key;
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?{
 ? ? ? ? ? ? ? ? ? ?//回溯时统计左右子树的值(min，max，sum)
 ? ? ? ? ? ? ? ? ? ?node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
 ? ? ? ? ? ? ? ? ? ?node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
 ? ? ? ? ? ? ? ? ? ?node.Sum = node.leftchild.Sum + node.rightchild.Sum;
 ? ? ? ? ? ? ? ?}
 ? ? ? ? ? ?}
 ? ? ? ?}
 ? ?}

数据结构与算法专题——第七题线段树 - 文章图片

内容总结

以上是互联网集市为您收集整理的数据结构与算法专题——第七题线段树全部内容，希望文章能够帮你解决数据结构与算法专题——第七题线段树所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/602204.html

来源：【匿名】

【上一篇】数据结构与算法专题——第六题树状数组【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【数据结构与算法专题——第七题线段树】教程文章相关的互联网学习教程文章

1. 定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作 2. 五个基本特性输入和输出算法具有零个或多个输入算法至少有一个或多个输出有穷性指算法在执行有限的步骤后，自动结束而不会出现循环，并且每一个步骤在可接受的时间内完成实际应用中合理的，可以接受的“有边界”确定性算法的每一步骤都具有确定的含义，不会出现二义性算法在一定条件下，只有一条执行路径，相同的输入...

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。一符号表在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，...

数据结构和算法绪论（一）【图】

1、什么是数据结构？程序设计=数据结构+算法物理结构+逻辑结构=数据结构一、4大逻辑结构：集合结构，线性结构，树形结构，图形结构，二、物理结构顺序存储结构，链式存储结构，（指针也需要存储空间）原文：https://www.cnblogs.com/zhzJAVA11/p/9896616.html

MySQL索引背后的数据结构及算法原理

摘要本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。文章主要内容分为三个部分。第一部分主要从数据结构及算法理论层面讨论M...

数据结构算法【代码】【图】

#include<iostream> usingnamespace std;/* 算法算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据...

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

目录Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历TagBinary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历给一个二叉树的root，返回其节点值从上到下遍历，奇数层从左到右遍历，偶数层从右到左。Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right...

数据结构和算法【代码】

找出那个特殊的字母给定两个字符串s和t，它们只包含小写字母。字符串t由字符串s随机重排，然后在随机位置添加一个字母。请找出在t中被添加的字母。示例如果字符串s = "abcd";，t = "abdec";，则输出为e。方法一：使用异或运算求和char FindTheDiffAlp(const std::string s, const std::string t) {const std::string st = s + t;char c = 0;for (std::size_t i = 0; i < st.size(); ++i) {c ^= st.at(i);}return c; }方法二：分别...

Java数据结构和算法（十二）——2-3-4树【代码】【图】

通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。本篇博客我们将介绍的——2-3-4树，它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。1、2-3-4 树介绍　　2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：　　①、有一个数...

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

符号表（3）——二叉查找树本系列文章主要介绍常用的算法和数据结构的知识，记录的是《Algorithms I/II》课程的内容，采用的是“算法（第4版）”这本红宝书作为学习教材的，语言是java。这本书的名气我不用多说吧？豆瓣评分9.4，我自己也认为是极好的学习算法的书籍。通过这系列文章，可以加深对数据结构和基本算法的理解（个人认为比学校讲的清晰多了），并加深对java的理解。符号表3二叉查找树二叉查找树1 代码框架2 节点表示3 取...

第4章数据结构算法【代码】

py内置数据结构算法常考常用内置的算法和数据结构sorted list/set/dict/tuple常用内置数据结构和算法数据结构/算法语言内置内置库线性结构list(列表)/tuple(元组)array(数组, 不常用)/collections.namedtuple链式结构collections.deque(双端队列)字典结构dict(集合)collections.Counte(计数器)/OrderedDict(有序字典)集合结构set(集合)/frozenset(不可变集合)排序算法sorted二分算法bisect模块堆算法heapq模块缓存算法functools.lr...

数据结构 - 相关标签

数据结构导论数据结构是什么数据结构习题数据结构严蔚敏数据结构与算法分析

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 数据结构与算法专题——第七题线段树

数据结构与算法专题——第七题线段树

内容导读

内容图文

一：线段树

二：代码

1: 在节点中定义一些附加值，方便我们处理RMQ问题。

2：构建(Build)

3：区间查询

4：更新操作

内容总结

内容备注

内容手机端

【数据结构与算法专题——第七题线段树】教程文章相关的互联网学习教程文章

数据结构：二算法

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

数据结构和算法绪论（一）【图】

MySQL索引背后的数据结构及算法原理

数据结构算法【代码】【图】

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

数据结构和算法【代码】

Java数据结构和算法（十二）——2-3-4树【代码】【图】

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

第4章数据结构算法【代码】

Java数据结构和算法之栈与队列【图】

数据结构和算法_队列

【uva 1471】Defense Lines（算法效率--使用数据结构）

数据结构和算法————二分查找【代码】

数据结构与算法-数据结构和算法概述、评判程序优劣、数据结构【代码】

数据结构 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程

首页 / 算法 / 数据结构与算法专题——第七题 线段树

数据结构与算法专题——第七题 线段树

内容导读

内容图文

一：线段树

二：代码

1: 在节点中定义一些附加值，方便我们处理RMQ问题。

2：构建(Build)

3：区间查询

4：更新操作

内容总结

内容备注

内容手机端

【数据结构与算法专题——第七题 线段树】教程文章相关的互联网学习教程文章

数据结构 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程

首页 / 算法 / 数据结构与算法专题——第七题线段树

数据结构与算法专题——第七题线段树

【数据结构与算法专题——第七题线段树】教程文章相关的互联网学习教程文章