简介

树状数组（Binary Indexed Tree，简称BIT），有时也被称作Fenwick树，是一种用于高效处理前缀和、区间求和、以及相应更新等问题的数据结构。它提供了比普通数组更好的方法来实现这些操作，特别是在需要频繁更新元素和查询前缀和的场景中。树状数组在时间复杂度和空间复杂度上都很优秀，实现也相对简单。

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。

• 结合律：$(x \circ y) \circ z = x \circ (y \circ z)$，其中$\circ$ 是一个二元运算符。

• 可差分：具有逆运算的运算，即已知$x \circ y$ 和 x 可以求出 y。

事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。

线段树简介

线段树（Segment Tree）是一种非常灵活的数据结构，它能够高效处理与区间相关的问题，如区间求和、区间最大值（或最小值）以及区间更新等操作。

线段树是一个二叉树，其中每个节点代表一个区间（或一个段），并且这个区间可以被分解成两个子区间，这些子区间分别由当前节点的两个子节点所表示。

线段树的思想源自于二叉搜索树，都有区间的概念，不过BST的节点是区间分割点，而线段树的节点本身就是区间的整体信息，这个整体信息可以是任何该区间的整体信息，只要该区间的整体信息可以由两个子区间的整体信息合并来即可，如区间和

最近在leetcode看到了一道题，很有意思，可以用动态规划解，也可以用Dijkstra算法来解，这道题最大的启发就是：

动态规划的每个节点就是图中的节点，状态转移方程其实就是两个节点之间的连线，我们可以用Dijkstra算法求解从开始节点到目标结点的最短路径。

最近在极客时间上买了一个关于K8S的课程，第一个部分讲的是Docker容器的基本原理，简单总结一下。

最近在项目中使用了vditor但是它的数学公式，流程图，脑图等都没法用，看了它的源码后，找到了解决方案，这里记录下。

最近拼多多的推金币比较火，就尝试想用一下2D的游戏引擎试一下效果，做了一个简单的Demo。

引擎选择的是Eva，采用这个引擎是因为它基于ECS的微内核架构，让扩展非常方便，同时也提供了几个官方的插件，足以支持大部分需求，它的渲染引擎插件是基于PixiJS，物理引擎插件是基于MatterJS，它的插件所依赖的版本比较低了，对于我来说还够用，如果有需要完全可以自己实现。

单源最短路径算法和多源最短路径算法的区别在于它们解决的问题不同。

单源最短路径算法是指在给定一个起点，计算该起点到图中其他所有顶点的最短路径。其中最著名的算法是Dijkstra算法和Bellman-Ford算法。Dijkstra算法适用于有向图中没有负权边的情况，而Bellman-Ford算法可以处理有负权边的情况。

多源最短路径算法是指计算图中任意两个顶点之间的最短路径。其中最著名的算法是Floyd-Warshall算法。Floyd-Warshall算法通过动态规划的方式计算任意两个顶点之间的最短路径，可以处理有向图和负权边的情况。

总结起来，单源最短路径算法解决的是从一个起点到其他所有顶点的最短路径问题，而多源最短路径算法解决的是任意两个顶点之间的最短路径问题。

贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离，是一种单源最短路径算法，支持存在负权重的情况

这是一道leetcode的中等难度的题目，代码不算复杂，但还是有一点可以记录下来举一反三。

最近在通过《代码随想录》训练关于贪心算法方面的题目，有了一个新的心得体会，在这里摘抄一下，就是，如果一道题目有多个维度，那先不要上来就尝试在多个维度同时做贪心，那大概率会让给自己的思路陷入混乱。