買了個阿里雲服務

有點太貴了。隨便跑點什麽 Memory 就 100%。

時常掉綫，不知道是不是網絡的問題。拿到公司 Network 環境一樣掉綫。

想搭個 Gatsby 玩玩，還是用自己的電腦吧。

Binary Search Tree

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 左、右子树也分别为二叉排序树。
• 没有键值相等的节点。

实现

Node:

1
2
3
4
5
6
7
8

let print = (key) => console.log(key)
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

什么是 Basic Authentication？

Basic Authentication 是一种 HTTP 协议的认证方式，它使用用户名和密码对客户端进行身份验证。
RFC 2617 定义了 Basic Authentication 协议，它规定了客户端如何向服务器发送请求，以及服务器如何验证用户名和密码。
当用户试图访问受保护的资源时，服务器会判断 HTTP Header 中的 Authorization 字段是否包含有效的 Basic Authentication 认证信息。如果没有，服务器会返回 401 Unauthorized 状态码，要求客户端提供认证信息，并在响应头中添加 WWW-Authenticate: Basic 字段。

Definition

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1. update(index, delta): 将delta加到index位置上。
2. prefixSum(index): 求 sum[1, index]的值。
3. rangeSum(from, to): 求 sum[from, to] 的值。

时间复杂度：

1. update(index, delta): 更新需要循环更新每一个parent的值，从index开始到最后一个parent。复杂度为O(n)。
2. prefixSum(index): 直接返回sum[index + 1]即可，复杂度为O(1)。
3. rangeSum(from, to): 直接返回sum[to + 1] - sum[from]即可，复杂度为O(1)。

Build

现在有个nums初始数组，通过这个数组构造一个BITArray。
构造Binary Indexed Array。

1. 实现insert(index, delta):

1
2
3
4
5
6

function insert(index, delta) {
  while (index < this.BITArray.length) {
    this.BITArray[index] += delta
    index += index & -index // BIT中，parent的index计算方法为：parent = child + (child & -child)
  }
}

2. 构造 BITArray:

1
2
3
4
5
6

function MyArray(nums) {
  this.BITArray = new Array(nums.length + 1).fill(0)
  for (let i = 0, len = nums.length; i < len; i++) {
    this.insert(i + 1, nums[i]) // 在每个index处循环插入，delta就是初始值。
  }
}

3. 实现sum(index):

1
2
3
4
5
6
7
8
9

function sum(index) {
  let sum = 0
  while (index > 0) {
    sum += this.BITArray[index]
    index -= index & -index // BIT中，child的计算方法为：child = parent - (parent & -parent)
  }

  return sum
}

4. 实现perfixSum(from, to)

1
2
3

function perfixSum(from, to) {
  return this.sum(to + 1) - this.sum(from)
}