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

閑著無聊看了看如何部署

公司内部有 k8s 集群,所以也需要學習如何寫 deploy 脚本.目前服務挂在 Travis CI 上,後續可能會使用自己的機器裝個 Github Runner 啥的…

步驟大致為:

1. 在 Travis 中登錄,然後選擇需要 watch 的倉庫
2. 編寫 deploy 文件,需要内部暴露字段的可以在 setting 中添加
3. 在 github 中拿到 person access token,添加到 Travis

因爲 blog 還不需要 build 和 test 的步驟,所以我的 deploy file 暫時還沒有這些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

language: node_js
node_js:
  - 10 # hexo目前似乎還不支持node 14版本

branches:
  only:
    - master # 需要監聽的branch

before_install:
  - npm install -g hexo-cli

install:
  - npm install
  - npm install hexo-deployer-git

before_script:
  - git config user.name "${username}"
  - git config user.email "${email}"
  - rm -rf themes/next
  - git clone https://github.com/theme-next/hexo-theme-next themes/next
  - cp assets/config/_config.yml themes/next/_config.yml # 我將自己的theme config存在assets中
  - cp assets/images/avatar.jpg themes/next/source/images/avatar.jpg
  - sed -i "s/github_token/${GITHUB_TOKEN}/g" _config.yml

script:
  - hexo clean
  - hexo generate
  - echo "Generation finished."
  - hexo deploy

notifications:
  email:
    - [email protected]
  on_success: change
  on_failure: always

October Plan

• React Hook: 首要完成的目標
• shell: 不知道能學到什麽程度
• Linux 命令: 不知道能學到什麽程度
• 優化之前的 code: 算是屎山了

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

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.

Boosting Flutter Performance with Frame-Based Rendering using keframe

Flutter is known for its smooth UI performance, but complex animations or frequent rebuilds can sometimes lead to jank. Frame-based rendering, also known as keyframe animation, offers a powerful technique to optimize these scenarios. This article explores how to leverage frame-based rendering in Flutter using the keframe package, focusing on FrameAnimation, FrameSeparateWidget, and SizeCacheWidget.

What is Frame-Based Rendering?

Traditional rendering in Flutter often involves rebuilding widgets every time their properties change. While efficient in many cases, this can become a bottleneck when dealing with intricate animations or rapidly changing data.

Frame-based rendering pre-calculates animation frames and stores them. During animation, the system displays these pre-rendered frames sequentially, minimizing constant rebuilds. This results in smoother animations and improved performance, especially on less powerful devices.