01/02/2019
Binary Indexed Tree (Fenwick Tree)

#What’s the problem that Binary Indexed Tree trying to solve?

Prefix Sum

Range Sum可以通过prefix sum来求得. 但BIT并不是直接solve range sum, 而是解决prefix sum的问题.

#Two Main Function in Binary Indexed Tree

getParent(x) = x - (x & (-x)), used for query
getNext(x) = x + (x & (-x)), used for update

#Why it works?

因为每个数都可以用2进制来表示, 比如:

  • 7 = 2^2 + 2^1 + 2^0
  • 10 = 2^3 + 2^1

因此可以把这些2^x 看作是binary indexed tree中的一个结点. 每个结点的parent就是当前结点去掉最右边一位1的结果, 比如:

  • 7的parent是6,6的parent是4, 4的parent是0
  • 10的parent是8,8的parent是0

那么在每次query prefix sum的时候, 从当前结点一路往上getParent, 得到的path sum就是结果.
而在每次update的时候, 从当前结点一路update getNext, 注意getNext不一定是和当前结点在一条path上(但getParent一定是一条path).

#Code

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
class BIT {
private int[] A;
private int[] bit;
private int n;
public(int[] A) {
this.n = A.length;
this.A = A;
this.bit = new int[n];
}
public void update(int index, int value) {
int delta = value - A[index];
while (index < n) {
bit[index] += delta;
index += (index & (-index));
}
}
public int prefixSum(int index) {
int res = 0;
while (index < n) {
res += bit[index];
index -= (index & (-index));
}
return res;
}
}

#Reference:

https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
https://www.youtube.com/watch?v=WbafSgetDDk&t=980s
https://www.youtube.com/watch?v=CWDQJGaN1gY&t=1s

11/04/2018
Binary Tree Leaf Node Iterator

Problem

⭐️⭐️⭐️⭐️⭐️

写一个Binary tree的leaf node iterator

Read More

09/16/2018
Binary Tree Traversals

Binary Tree Traversals

Read More

06/03/2018
Full Tree vs Complete Tree vs Perfect Tree

#Perfect Tree

1
2
3
4
5
6
7
8
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x

#Complete Tree

1
2
3
4
5
6
7
8
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x

#Full Tree

1
2
3
4
5
6
7
8
x
/ \
/ \
x x
/ \
x x
/ \
x x

03/11/2018
Graph

Graph

总结一下Graph的所有算法

Questions to Ask

Before any graph problems, ask yourself the following 4 questions:

  1. Directed or Undirected?
  2. Weighted or Unweighted?
  3. Sparse graph or Dense graph?
  4. Adjacency Matrix or Adjacency List?

Graph Theory Problems with Cheat Sheet

  1. Search
  2. Topological Sort
  3. Cycle Detection
  4. Shortest Path Problem
    • Single Source Shortest Path Problem (SSSP)
      • Topological Sort (DAG)
      • Dijkstra (without negative edge)
        • Lazy Implementation
        • Eager Implementation with IndexHeap
      • Bellman-Ford (without negative cycle)
    • All Sources Shortest Path Problem
      • Floyd-Warshall
    • Longest Path Problem
  5. Connectivity
    • Union-Find
    • Strongly Connected Component
      • Tarjan’s Algorithm
      • Kosaraju’s Algorithm
    • Bridges (Cut Edges)
    • Articulation Points (Cut Vertex)
  6. Eulerian Path / Eulerian Cycle
  7. Hamiltonian Path / Hamiltonian Cycle
  8. Minimum Spanning Tree
    • Prim’s Algorithm
      • Lazy implementation
      • Eager implementation with IndexHeap
    • Kruskal’s Algorithm
  9. Traveling Salesman Problem
  10. Network Flow Problem
    • Ford-Fulkerson
    • Edmonds-Karp
    • Capacity Scaling
    • Dinic Algorithm
  11. Bipartite Problem
    • Maximum Cardinality Bipartite Matching (MCBM)
Read More

03/04/2018
Indexed Heap

03/01/2018
Minimum Spanning Tree

#Minimum Spanning Tree

Given: Undirected Graph G with positive edge weights (connected)

Definition: A spanning tree of G is a subgraph that is both a tree (connected and acyclic) and spanning (includes all the vertices)

Goal: Find a spanning tree with minimum weight

#Solution

  1. Brute Force: Find all spanning tree
  2. Kruskal’s Algorithm
  3. Prim’s Algorithm

© 2020 ReeeStart with help from Hexo and Twitter Bootstrap. Theme by Freemind.