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)
}

在某个论坛有人问了下面的一段代码

1
2
3
4
5
6
7
8
9
10
11
12

function f() {
  console.log("outside")
}
function a() {
  f()
  {
    function f() {
      console.log("inside")
    }
  }
}
a()

问的是为什么在浏览器中是f is not a function。
这个问题其实很好回答，存在函数提升，但是仔细想想又不对，因为函数提升是把整个函数都提升到当前作用域，所以按理来说 f 并不会是undefined。
如果按照函数提升的话，结果应该是像这样：

1
2
3
4
5
6
7
8
9
10
11

function f() {
  console.log("outside")
}

function a() {
  function f() {
    console.log("inside")
  }
  f() { }
}
a()

所以结果应该是inside才对，用 IE7 可以发现结果确实是 inside。
那这里为什么是 undefined 呢？
后面那位兄弟说在阮一峰的《ES6 入门》中说道，ES6 规定块级作用域中的函数定义规定为函数表达式。如果是定义为函数表达式的话，那就会像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function f() {
  console.log("outside")
}

function a() {
  var f
  f()
  {
    var f = function f() {
      console.log("inside")
    }
  }
}
a()

这么一来这个undefined就可以解释了，因为只存在变量提升，而还未定义，所以就会出现undefined。但是那本书后还加了一句，浏览器并未遵循实现。
后面在 starkoverflow 上找到了一个老哥的回答，他的解释为这是因为strict & non-strict mode的不同。

• let 和 const 在两种模式下行为一样
• function 在两种模式下的行为就不是一样的，因为浏览器会扩展非严格模式，从而兼容老代码。

所以，在strict mode中，第一段代码输出的是outside，non-strict mode中就会报错，因为会变成下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function f() {
  console.log("outside")
}

function a() {
  var f // function-scoped
  f()
  {
    let f1 = function () {
      console.log("inside")
    } // block-scoped
    f = f1
  }
}
a()

MDN 中关于Block-level functions in non-strict code的也只有一句话： Don't.