演算法數據結構中有哪些奇技淫巧？

01-11

演算法數據結構中，有哪些技巧或使用方式能讓你覺得「卧槽，還能這樣用」？想要的就是那種特別簡潔，理解以後又眼前一亮的技巧~

Yao"s protocol.

「如何讓兩個女士比較出誰更胖——在她們都不想泄漏體重的前提下？」

問題是這樣的：假設 Alice 手上有一個隱私函數 f，Bob 有隱私數據 x，那麼請為他們設計一個協議，讓雙方互相不給任何人透露自己隱私的情況下，計算出 f(x) 的數值？（從 f(x) 的結果推斷 x 或者 f 不算在內；雙方始終遵守協議。）

實現是這樣的：考慮一個 k 個 bit 到一個 bit 的簡單函數 f（更複雜的函數可以簡化到這個樣子），alice 可以打出 f 的真值表來，然後她產生 k+1 對隨機數，表示 k 個輸入 bit（ $j_{n, {0,1}}$ ）和輸出 bit 的 0/1 值（ $r_{{0,1}}$ ）。

接著她按照這些隨機數加密真值表，比如如果 f(1, 1)=0，則她用兩個隨機數作為密鑰加密 $r_0$ 產生一個密文 $E[j_{1,1}, j_{2,1}](r_0)$ 。她可以把加密的真值表連同表示結果的隨機數 $r_{{0,1}}$ 發給 Bob。

接下來 Bob 需要按照自己的數據（x）找 Alice 要 k 個隨機數解碼他拿到的真值表，真值表中只有一項可以被解碼，解碼的結果就是 f(x)，其他的則無法解碼。

要隨機數的過程是基於 Oblivious Transfer，這個協議要求：

Bob 根據自己的選擇獲取 Alice 兩條私密消息 $m_0,m_1$ 中的一條，另一條則無法解密；
而 Alice 不能得知 Bob 的選擇。

過程是：

Alice 生成 RSA 公鑰-密鑰對 $(e, d, N)$ ，她把公鑰 $(e,N)$ 發給 Bob，Bob 根據自己的選擇 $cin{0,1}$ 獲取 $m_c$ 。以下計算均在 $mathbb{Z}_N$ 上進行。
Alice 生成兩個隨機數 $x_0,x_1$ 發給 Bob。
Bob 生成隨機數 k，計算 $v=x_c+k^e$ 發給 Alice。由於 k 是私密的，Alice 無法解密出 c 來。
Alice 計算 $k_0=(v-x_0)^d, k_1=(v-x_1)^d$ ，發送 $m_0$ 給 Bob。
Bob 計算 $m_c=m$ （因為 $k_c=k^{ed}=k$ ），而對於另一條消息，他就無法成功解碼。

————————————————————————————————————————————

有關 @aricatamoy「為什麼不用天平」，那麼請問：兩個人該怎麼做才能保證天平上面沒被動過手腳，暗地裡收集她們的體重呢？

好像沒人提到fractional cascading？本身就很強大，在很多數據結構中應用廣泛，比如優化range tree一個log n。先mark，等學完車補上。

============================我是來填坑的============================

我們從一個簡單的演算法題開始考慮：給出k個有序的數組 $L_1, L_2, cdots, L_k$ ，每一個長度為n；你可以對該數組進行線性時間的預處理，然後回答如下詢問：給出x，回答每個數組中第一個小於x的元素是什麼。

常規的想法是對於每個數組二分查找，複雜度是 $O(k log n)$ ，而fractional cascading通過一個簡單的idea允許我們做到 $O(k + log n)$ 。

進行如下的預處理：令 $L$ ；然後遞歸構造對於每一個 $1 leq i < k$ ，令 $L$ 為將數組 $L_i$ 的全部元素與 $L$ 中偶數位置的元素歸併而得到的新數組。這個預處理可以在線性時間 $O(k n)$ 內完成，因為我們發現對於任何 i 滿足 $|L$ 。

（圖片來源：Erik Demaine 6.851 Lecture 3 Note, Figure 10）

同時每個元素計算左右兩個指針，對於 $L$ 中的元素（上一段中，它是通過兩個有序數組歸併得到的）：

1) 如果來自 $L_i$ ，則維護左右第一個來自 $L$ 的元素的位置；

2) 如果來自 $L$ ，則維護左右第一個來自 $L_i$ 的元素的位置；

這類指針可以在線性時間內通過遞推求得。

對於詢問x，首先在 $L$ 中二分並使用指針找到對應的位置。然後利用左右指針p1 p2，找到對應在 $L$ 中的位置。由於p1 p2在 $L$ 中一定只隔一個元素，故我們只要掃描常數個位置就能找到 $L$ 中的第一個小於x的元素（且原本屬於 $L_2$ ）。以此類推，得到了 $L_2$ 的答案後，只要常數時間就能得到 $L_3$ 的答案。故總的時間複雜度為 $O(log n + k)$ ，即第一次使用了二分，之後每次都是常數查找。

該方法還使用於range tree 和 half-plane range reporting data structure（給出平面上一些直線，構造一個線性空間的數據結構，可以在 $O(log n + m)$ 的時間內回答一個點的上方有哪些直線，這裡m是答案數量）等等數據結構中來優化掉一個log n因子。

其他奇技淫巧陸續更新中……

===========================

SPFA (Shortest Path Faster Algorithm)

說到單源最短路徑，大家常常會想到的是Dijkstra演算法（發音：荷蘭語：[??tsx?r ??ib? ?d?ikstra] ）。但是對於帶有負權的單源最短路徑的話，可能就只能求助於Bellman Ford演算法了。但是BF演算法的時間複雜度是 $O(VE)$ ，有沒有更快的解決辦法呢？

這裡就要介紹一下西南交通大學的段凡丁於1994年發表的《關於最短路徑的SPFA快速演算法》了。SPFA演算法的在該篇文章中的期望時間複雜度 $O(E)$ 的證明據說是錯誤的，但是因為其傑出的實際運行效率和簡單的實現而讓ACMer都推崇備至。

SPFA(G, s): for each vertex v in G.V: v.d = ∞ s.d = 0 push s into Q while Q is not empty: pop u from Q for each edge (u, v) in G.E: if u.d + w(u, v) &< v.d then: v.d = u.d + w(u, v) if v is not in Q then: push v into Q

Dijkstra演算法中的隊列保存的是所有未確定的點，所以需要每次從中選取最短路徑估計最小的頂點的鄰邊來進行鬆弛。而SPFA演算法中的隊列保存的是所有鬆弛過的邊對應的頂點。上述兩種演算法與BF演算法相比，優勢都體現在不是盲目地對所有邊進行鬆弛，故可以得到比BF演算法更好的性能結果。

但是Dijkstra演算法中的最短路相當於在一點一點「生長」，如果出現負權邊，那麼個生長的過程就需要繞回去，這對於Dijkstra演算法來說是做不到的。而BF演算法並不是依靠這種「生長」的辦法，所以它可以做到這一點。因此，SPFA作為BF演算法的隊列優化版，解決了Dijkstra演算法面對負權邊的問題，又避免了BF演算法在性能上的劣勢，是一個實際運用中很受歡迎的演算法。

跳錶：

由於鏈表不是call-by-rank而是call-by-position的一類線性數據存儲結構。所以鏈表的查找沒有辦法應用例如有序數組中二分查找一類的方法，只能通過線性搜索進行元素的查找。

而對於一個有序鏈表來說，如果我們可以在查詢的時候先隨機跳過大量元素，再逐步減少跳躍的幅度，鎖定到我們最終查找的元素上時，那麼我們的搜索成本將會得到極大地減少。Skip list就是運用這個原理設計出來的。

例如上圖當中，如果要搜索數字19的話，需要從左側頭結點開始，跳到下一個結點21，發現21 &> 19則跳回去到下一層。下一層下一個結點為9，再後面一個是21 &> 19，又跳回9並下鑽。下一個結點為17 &< 19則繼續後跳到21，再次發生21 &> 19，則往回跳到17並下鑽，最後到達待搜索的節點19的位置上。

跳錶有著類似平衡BST的時間複雜度，而實現更簡單，常係數更小，空間佔用更小。這些特點常常使得它作為平衡BST的替代品被應用。

平方根倒數速演算法：

在利用到3D圖形渲染的一些遊戲或者程序當中，法向量的單位化計算顯得尤為重要。在三維歐幾里得空間當中，某一向量 $v=(v_x,v_y,v_z)$ 的單位化是指計算 $v^prime = frac{v}{||v||_2}$ 。其中 $||v||_2$ 表示向量 $v$ 的二範數，也即 $||v||_2=sqrt{v^2_x+v^2_y+v^2_z}$ 。其中設 $x=v^2_x+v^2_y+v^2_z$ ， $x$ 的計算主要是乘法與加法，所以性能上不會有太大瓶頸。而計算 $v^prime = v imes x^{-frac{1}{2}}$ 的時候， $x^{-frac{1}{2}}$ 數值求解的速度如何將會極大影響向量單位化的運行效率。平方根倒數速演算法正是為了解決這個問題而出現的。

float Q_rsqrt(float x) { float x2 = x * 0.5F; int i = *(int*)x; // evil floating point bit level hacking i = 0x5f3759df - (i &>&> 1); // what the fuck? x = *(float*)i; x = x * (1.5F - (x2 * x * x)); // 1st iteration return x; }

這個方法從本質上來介紹的話，就是先近似計算一個初始值，然後帶入牛頓迭代法來計算最後的較為精確的 $x^{-frac{1}{2}}$ 。涉及的中間變數有 $x o -frac{1}{2}log_2{x}= log_2{x^{-frac{1}{2}}} o x^{-frac{1}{2}}$ 。首先計算i = *(int*)x是為了獲得浮點數 $x$ 對應的整數表示 $I_x$ 。然後利用 $I_x$ 去求出 $log_2{y}=-frac{1}{2}log_2{x}$ 中 $y$ 對應的整數表示 $I_y$ ，這也就是上述注釋「what the fuck」對應的那句i = 0x5f3759df - (i &>&> 1)的作用。

求得了整數表示 $I_y$ 以後，將該數轉換回浮點數，也即求到了 $y=x^{-frac{1}{2}}$ 的近似值。最後一句使用牛頓迭代法對 $y^2-frac{1}{x}=0$ 進行一遍迭代求解，也就是將上面得到的 $y$ 帶入牛頓迭代法的公式當中作為初始值計算一遍，最後得到較為精確的結果。

這個演算法的核心地方在於如何利用 $log_2{y}=-frac{1}{2}log_2{x}$ 這一等式得到 $I_x$ 與 $I_y$ 的關係，而這也就是0x5f3759df的重要意義所在。具體的數學推導以及中間的「魔數」0x5f3759df是怎麼算出來的可以參見維基百科Fast inverse square root。

珠排序：

珠排序作為一種自然排序演算法，在計算機當中沒有辦法找到一種很好的實現來進行模擬，但是，並且只能為正整數序列進行排序。但是其中的思路卻真的算是一種奇技淫巧了。

對 $n$ 個正整數 ${k_i|i=1,2,cdots n}$ 進行排序的話，我們就造 $m=max{k_i}$ 根柱子。然後對於每一個正整數 $k_i$ ，我們就把它想像成 $k_i$ 個珠子。我們將這 $k_i$ 個珠子分別串在在第1根、第2根、……第 $k_i$ 根柱子上。

所有數都串完了以後，將這 $m$ 根柱子垂直放置下來，所有珠子都隨重力下落，然後每行上（不是每根柱子上）的珠子數，就是最後的排序結果。

Duff"s Device：

從一個指針from向另一個指針to拷貝count個位元組，你打算怎麼做？

正常的做法是

do { *to++ = *from++; } while(--count &> 0);

這段代碼當中，這句--count &> 0的會被判斷count次。

那麼真的需要判斷這麼多次么？讓我們來看看Duff"s Device的實現是怎麼做的

void send(int *to, int *from, int count) { int n = (count + 7) / 8; switch (count % 8) { case 0 : do { *to++ = *from++; case 7 : *to++ = *from++; case 6 : *to++ = *from++; case 5 : *to++ = *from++; case 4 : *to++ = *from++; case 3 : *to++ = *from++; case 2 : *to++ = *from++; case 1 : *to++ = *from++; } while (--n &> 0); } }

這段代碼巧妙地將switch和while雜糅在一起，不僅每次8個位元組進行拷貝，而且對末尾不足8個位元組的部分做了精巧的處理，通過循環展開減少了循環判斷的次數，從而優化了性能。

尾遞歸：

給你一個單鏈表的頭結點，讓你得到這條鏈表的長度是多少，要求用遞歸進行編寫的話，你會怎麼做呢？

正常的做法是

int linked_list_length(node *head) { if (head-&>next == NULL) return 0; else return linked_list_length(head-&>next) + 1; }

這段代碼的問題在於什麼呢？如果鏈表非常長的話，成百上千次的遞歸壓棧將會耗盡棧空間，造成棧溢出。如果我們使用尾遞歸的話，就可以這樣

int linked_list_length(node *head, int len) { if (head-&>next == NULL) return len; else return linked_list_length(head-&>next, len + 1); }

尾遞歸與普通遞歸最大的區別在於，整個遞歸調用佔據了整個return後面的部分。由於它在整個方法的最後才被調用，那麼之前函數壓棧保留的所有局部變數等等信息都不影響下一次遞歸調用，所以本次方法中棧內的信息可以被清空，讓下次調用可以重複使用這段棧空間。

所以尾遞歸的本質，其實就是將這次遞歸方法當中的必要信息，傳遞到下次遞歸當中，從而保證return後面是一個完整的遞歸函數調用而不是一個表達式。

二級指針刪除單向鏈表中結點：

這個利用二級指針（pointers-to-pointers）優化單向鏈表當中的刪除操作，是Linus在Linus Torvalds Answers Your Questions上就什麼才是真正的「core low-level kind of coding」所提出的一個例子。當你要寫一個單向鏈表當中根據某個特定條件來剔除結點的函數，你會怎麼寫呢？

正常的做法是

typedef bool (*remove_fn)(const node *n); void remove_if(node *head, remove_fn rm) { for (node *prev = NULL, *curr = head; curr != NULL; ) { node* next = curr-&>next; if (rm(curr)) { if (prev) prev-&>next = next; else head = next; delete curr; } else prev = curr; curr = next; } }

其中remove_fn是一個函數指針類型，表示判斷是否刪除結點的條件。這裡的實現通過維護一個prev指針來進行結點的刪除，需要判斷prev是否為NULL來確定當前刪除的結點是不是頭結點。這種實現方式是被Linus所唾棄的「This person doesn』t understand pointers」。那麼使用二級指針對上述代碼進行優化的話，就是

void remove_if(node **head, remove_fn rm) { for (node **curr = head; *curr; ) { node *entry = *curr; if (rm(entry)) { *curr = entry-&>next; delete entry; } else curr = entry-&>next; } }

上述代碼的重點在於二級指針curr。循環開始時，二級指針curr指向頭結點的指針。如果頭結點是需要刪除的結點的話，*curr=entry-&>next就相當於*head=(*head)-&>next，也即修改頭結點的指針指向下一個結點。

如果要刪除的節點不是頭結點的話，由於curr是通過entry-&>next更新的，所以要此時curr指向要刪除的節點的上一個節點的next指針，而entry指向的是要當前要刪除的指針，此時*curr=entry-&>next就相當於prev-&>next=entry-&>next，從而完成當前節點的刪除。

歡迎關註：

http://weixin.qq.com/r/2zlDW1XEWwgkrRE492zJ (二維碼自動識別)

Union-find algorithm (path halving)

簡單、無遞歸，保障時間複雜度

int find(x) { while (djs[x] != x) djs[x] = djs[djs[x]], x = djs[x]; return x; }

`Variant` segment tree (學名不明)區間表示

從[0,n)開始，每次使用 floor((l+h)/2) 的區間折半策略。如 [0,5) 得到 [0,2) [2,5) [0,1) [1,2) [2,3) [3,5) [3,4) [4,5)。

可以用如下映射法則給區間編號：

int id(int l, int h) { return l == h-1 ? 2*n+l : l+h; }

給定 x，枚舉滿足 (y x) == y 的 y

for (int y = x; ; y = y-1 x) { // process y if (! y) break; }

所有m位01串中枚舉包含mm個1的

int large = (1&<&&> __builtin_ctz(g)+1; }

32-1-__builtin_clz(x) 計算 floor(log2(x))
Topological sort

degree向量中減少爲0的元素可以組織成一個棧

for (i=0; i&



Sieve of Eratosthenes 求 Euler phi

iota(phi, phi+n, 0);

for (i=2; i&


Fenwick tree (我喜歡下標從0開始)

void add(int x, int y)

{

  for (; x &< n; x |= x+1)
    fenwick[x] += y;
}

// sum of [0,x)
void getSum(int x)
{
  int s = 0;
  for (; x; x = x-1)
    s += fenwick[x-1];
  return s;
}

實際上 add 可以從遞增變爲遞減，而 getSum 從遞減變爲遞增
void add(int x, int y)

{

  for (x++; x; x = x-1)

    fenwick[x-1] += y;

}

// sum of [x,n)

void getSum(int x)

{

  int s = 0;

  for (; x &< n; x |= x+1)
    s += fenwick[x];
  return s;
}



Binary heap 根據鍵查位置

make_heap push_heap pop_heap 等，重載 operator= 再根據 this 指針更新鍵到位置的映射。實際上沒啥用，自己實現更方便
在那個NOIP/NOI不能用STL的年代，我琢磨了怎麼重載操作符使 stl_set.h 支持節點size信息。但STL實現的節點指針修改推測不是可組合的，很難實現。


Treap類似Splay維護dynamic sequence

在查詢區間兩端插入低priority的節點，使得區間對應的節點形成一棵子樹並被提升到接近根的位置，可以直接讀出monoid和信息。
這樣做不清楚時間複雜度會變成什麼樣。


Top-down Splay tree

top-down Splay tree可以額外維護monoid域，left/right spine表示的節點如果上下倒置則可以省去parent指針，參見&
如果是group的話有稍簡單的做法，無需倒置spine上的節點：&


Wavelet tree

俗稱「劃分樹」。文獻中描述Wavelet tree時通常以字母表作爲劃分依據，每個區間對應一個字母表區間，當只剩一個字母時劃分結束成爲葉區間
競賽中常以rank(對於相等元素，先出現的rank小)爲劃分依據，這樣實現比較簡單。如果以字母表爲劃分依據的話，Wavelet matrix性能更高(減少了select rank操作數)


Strongly-connected components

Kosaraju"s algorithm、Tarjan"s SCC algorithm、Gabow"s SCC algorithm產生SCC的順序是topological order或逆序的，相對於收縮SCC後得到的圖而言
求2-SAT的任一方案時，根據 x 與 ~x 所在SCC的標號大小來判定 x 取 true/false。採用 Tarjan"s SCC algorithm 只需要一次DFS


Stack migration

競賽中偶有使用DFS等遞歸演算法會棧溢出的情況
Windows PE可執行文件可以配置棧大小(`#pragma comment(linker, "/STACK:16777216")`)，Linux x86/64可以遷移esp/rsp
const size_t STACK_SIZE = 16*1024*1024; // ulimit -s =&> usually 8 MiB

char st[STACK_SIZE];

void callee()

{

  int g;

  scanf("%d", g);

  printf("g=%d

", g);

}
void with_stack()

{

  static long sp;

  asm volatile("movq %%rsp, %0

	"

      "movq %1, %%rsp

	"

      : "=g"(sp) : "g"(st+STACK_SIZE) : "memory");

  callee();

  asm volatile("movq %0, %%rsp

	"

      : "=g"(sp) :: "memory");

}
int main()

{

  with_stack();

}


對編譯器瞭解很少，某些用例可能需要修改這個代碼
比如某些情況下棧會標記爲可執行，此時需要標記`st`所在segment權限可執行等。


Shunting-yard algorithm

operator-precedence grammar的特殊情形。常見實現會制定一張 |操作符|^2 的表格。
每個操作符有 in-stack 和 incoming 兩種狀態，判斷優先級根據 in-stack priority 和 incoming priority 即可，可以把 |操作符|^2 的表格簡化爲 2*|操作符|
優先級相等時代表兩端爲 terminal symbol 的 production 的 reduction，比如 `(` 與 `)` 的抵消


Tarjan"s offline lowest common ancestors algorithm

可以在計算LCA的同時處理樹上路徑的monoid查詢
int find(int x)

{

  if (djs[x] == x) return x;

  int y = djs[x];

  djs[x] = find(y);

  info[x] = mconcat(info[x], info[y]); // sum of info[x]  info[y]

  return djs[x];

}

void tarjan(int u)

{

  djs[u] = u; // MakeSet

  info[u] = ...... // sum of path from u to djs[u]

  for each query `q` with one endpoint at `u`

    v = other endpoint of `q`

    if djs[v] == -1

      lca = find(v)

      qq[lca] &<&< (query_id, u, v, lca)
  for each edge `e` with one endpoint at `u`
    v = other endpoint of `q`
    if djs[v] == -1
      tarjan(v)
      djs[v] = u
      info[v] = calculated info of edge (u,v)
  for each LCA result (query_id, x, y, u) of `qq[u]`
    find(x)
    find(y)
    result of query_id = mconcat(info[x], info[y])
}


如何判斷一個鏈表中有閉環？
如果有閉環，如何確定閉環的起始節點？
這個問題是我們數據結構課的老師(同時還是學校ACM隊教練)在課堂上讓我們討論研究的，整整討論了一節課吧。其基本知識僅僅是鏈表，但這個問題卻非常有意思。大家不斷討論中，各種方法越來越優化，最後的最佳演算法真是讓人眼前一亮。
後來實習面試時，一面考官在問了一堆簡單的排序演算法後說要問我一個難一點的問題，然後就問了上述的第一個問題。我說了答案後順便還說了第二個問題的答案。他一臉驚訝地問我是不是遇到過，我告訴他我們上課講過…
-----更新-----
（下有答案）
判斷鏈表有閉環：
鏈表頭部設置兩個指針，一個步長為1，一個步長為2，向前走，能相遇就是有環。
確定閉環起點：
（續）相遇後，一個指針不變，一個指針重置鏈表頭，步長均為1，再次走，相遇時即為環的起點。（謝 @Wexley Zhou）
-----更新-----
評論區眾神出沒，指出這只是Floyd判圈演算法，不能算技巧。長知識了，謝。
鏈接：wikipedia:Floyd判圈演算法

看到答案中很多人說的其實是不常見的一些演算法和數據結構（或者只在書上見過的），我理解的奇技淫巧是非常規的那種
比如，做AVL或紅黑樹的時候，每個節點需要保存一個平衡因子，AVL最小可以用2bit，紅黑樹1bit，然而在C中如果定義單獨欄位，至少要1byte，如果考慮位元組對齊，在64位環境下甚至可能佔8byte，所以最好是擠出bit來存這些，有人注意到，由於malloc或new返回的一般都是按4或8位元組對齊的，指針值末尾兩個bit恆為0，所以就把每個節點的left和right指針用起來了，當然每次存取需要位運算下，用一點效率損失來提高空間利用率，當然如果申請的地址不是按4對齊就不行了

並查集的路徑壓縮:
並查集是用來解決集合查詢/合併問題的經典方案，
它構造了一個森林，森林中每棵樹代表一個集合。 
初始時對於所有的節點設 x.parent = x，表示每個節點都是樹根，代表一個集合。
查詢一個節點所屬集合時，遞歸返回節點所在樹的根節點:
def find(x):

  if x.parent != x:

    return find(x.parent)

  return x


合併時只需將一個節點的根的parent指向另一個根,
這樣就把兩棵樹合併為了一棵
def union(x,y):

  xRoot = find(x)

  yRoot = find(y)

  xRoot.parent = yRoot


並查集本身是一個巧妙的設計，
但隨著不斷的union操作容易帶來樹深度過深，
導致效率降低的問題(查詢操作複雜度為樹的深度)，
於是就有個神奇的路徑壓縮策略，
只對find演算法進行了小改:
def find(x):

  if x.parent != x:

    x.parent = find(x.parent)

  return x.parent


增加一個更新x.parent操作，
每次查詢之後，從根到x的長度為k的路徑，將更新為k條長度為1的路徑，
使得並查集的操作從O(n)直接降到了介於與的一個值。
具體的複雜度分析見
Cormen, Thomas H. Introduction to algorithms. MIT press, 2009. 這本書的21.3，
只使用路徑壓縮的話，
執行n次初始化,最多n-1次union，與m次find的總時間，在最壞情況下是
上述章節里還討論了另外的一些優化，感興趣的同學可以自行閱讀。
當年是在做一道需要反覆查詢的題的時候，
自己YY出了集合查詢的基本思路(跟基礎並查集差不多，不過是非遞歸的)，
但是受困於每次查詢節點的O(n)的操作，無法AC，
然後有人告訴我這道題用"並查集"可以解決，
查了一下資料之後，驚為天人... 
不得不說前人的智慧實在太強大...

按照我的理解，奇技淫巧指的是各種繞過出題人意圖的解法。
1分塊大法。
分成根號n個塊進行平方級的預處理，然後做線性的查詢。
最終的複雜度是n^1.5，由於常數比nlogn的演算法小很多，效率並不差多少，但是代碼量顯著地小。
2桶排序。
還記得那年，int的上限是32767，開一個小小的數組就可以裝下所有值。
3卡時搜索。
不用一次卡時搜索怎麼知道自己是不是歐洲人？
4騙分導論加人品導論。

Radix Sort·改
對長度為n的數組的運行速度為O(kn)，對於int32而言k的最大值為8
void RadixSortGai(ref List&[] array)

{

    for (var exp = 0; exp &< sizeof(int) * 2; exp += 4)
    // C# sizeof返回值是以byte為單位，所以實際做的是sizeof(int) * 8 / 4
    {
        var digits = new List&[16];

        foreach (var element in array)

            digits[element &>&> exp  15].Add(element); // 右位移然後取後四位

        array = List.Concat(digits); // 把所有array合為同一個，該方法大概得自己寫

    }

}



可持久化也許可以算

達夫機器

融合樹(Fusion tree)的sketching大法。利用了一些位運算的技巧。好麻煩不想更了。
------------------------------------
卧槽題目里要簡潔啊...當我什麼都沒說。

有沒有人和我一樣覺得Boost里到處都是奇技淫巧……

O(1)計算兩個10^18級別的數的乘積模p
ans=(a*b-(long long)((long double)a/p*b+EPS)*p)%p


講下原理。總的原理是。而後面的則是計算了實數的在取整乘p。由於C++中long double的精度超過了18位，而是10^18級別的，因此可以保證結果正確。
式子里兩次乘法運算超過了long long的範圍，由於C++會高位會溢出，忽略符號位相當於是在模的意義下做。由於最終結果在以內，因此結果正確。

『奇淫技巧』（哈哈）就算了，不過倒是有一些私藏小技巧
比如鏈表問題，有三種通用技巧


造一個頭結點指向傳來的 node，有效簡化循環不變式
雙指針或者多指針
try


1) Persistant Data Structure: 函數式編程中不讓有state，比如A=[2,3], B=1::A (insert 1 入A的0位置)。 &<此時B=[1,2,3],A=[2,3]&>
怎麼樣快速的實現這個東西，你可以簡單粗暴的說A就像一個copyonwrite ArrayList一樣，寫時總是複製，但這樣太低效了，於是persistant data structure提供如下方案
從原來O(n)時間到O(1)時間。2) Binary Index Tree: 
長文請見topcoder上的tutorial：Binary Indexed Trees
此處僅表達奇技淫巧的隻言片語:
假設我有一個list A=[1,2,3,4,5];
然後我想要一種數據結構支持1)update A[i]的數字和 2)求sum(k=0..i)A[k],
兩種笨蛋方法分別是:
1) Update O(n) Sum O(1) 就是pre-compute每一個i的sum(k=0..i) A[k]，然後更新的時候更新所有的sum A(k)的值，既然已經pre compute 好了那麼只要直接return就好了.
2) Update O(1) Sum O(n) 就是什麼都不做，直接從頭開始累加就好了(蠢哭了)。
然後Binary Index Tree給出的聰明辦法是:
Update O(lgn) Sum O(lgn)
如圖所示，首先我們在list內部儲存1-indexed 有效長度為n的list, 此list中16處存A[1]~A[16]的和，8處存A[1]~A[8]的和 6處存A[5]~A[6]的和。
簡單來說，把此list中的index翻譯成二進位，比如說六就是 00110，那麼這一個index存的長度就是他倒著數第一次出現一的那一位的大小，此例中6的大小為2的一位是最後出現1的，所以6就存兩個東西，以6結尾的和。
然後我們要找出有效快速update和sum的方法
1) Sum 很簡單，向下掃，比如說我在位置11,他的二進位是1011,那麼根據list中存的每一個值都是一段A的sum的定義，sumA[1..11]=sumA[1..8]+sumA[9..10]+sumA[11].所以我只要返回list[11]+list[10]+list[8]就可以了。
這張圖給了一個相似的例子:
然後update的話我們只需要「貫通」的感覺：
比如說我要讓A[11]加上3，那麼我想知道 在list的那些部分的和是包含A[11]的，嗯有11，12和16.
我分別對者三個數來+3.
這個演算法的奇技淫巧還不僅僅在於演算法的優美，更在於寫起來的簡便，(以下bit 黑科技)
根據topcoder說，update+sum(或者叫query)兩個函數加起來不需要超過10行，
而我現在看到最短的update兩行，sum四行：Range updates with BIT / Fenwick Tree
# Add v to A[p]

update(p, v):

  for (; p &<= N; p += p(-p))
    ft[p] += v 	 

# Return sum A[1...b]	 
query(b): 	
  sum = 0 	
  for(; b &> 0; b -= b(-b))

    sum += ft[b]

  return sum


#感受一下人家的for loop...


今天寫不動了lol 過兩天更新Binary Search和Minimum Window

暫時想到最奇葩的應該是SG函數？把一類博弈化為一個數學函數。。。定義了一個mex的運算表示最小沒出現在集合里的非負整數。。。。然後多個博弈遊戲的合成就是SG函數值的異或。。總之就是用位運算，集合論來解決一個博弈問題。。。

現在這兩個回答說的不都屬於是編程中的奇技淫巧么，而不是演算法與數據結構中的奇技淫巧。
等我有時間，想想有什麼演算法與數據結構的。

以上很多朋友都說了各種數據結構中的精巧設計，我這裡再補充一個好玩的，就是Linux內核中關於鏈表的實現。
一般的鏈表都是專門有一個鏈表數據結構，然後這個數據結構中有各種元素以及前後向指針。
但在Linux內核中，鏈表數據結構並不包含任何實際元素，就只有簡單的前向後向指針，然後在實際的特殊數據結構里包含這個鏈表數據結構，大大提高了鏈表的可復用性。
struct list_head {
                struct list_head *next, *prev;
            }

以前自己實現hash map的時候都是用的 int index = hash % (length)


今天下午無聊沒事做看了下java的hashmap源代碼。
發現它是
static int indexFor(int h, int length) {

    return h  (length-1);

}


在length是2的冪次方的前提下，進行 h  (length-1)操作可以達到和取餘一樣的效果，但是效率比%高多了。

  推薦閱讀：


※不斷扔骰子，扔到總和大於22的時候喊停，問這個時候總和最可能是多少？
※大學階段，你是怎麼樣進行時間管理的？
TAG:演算法 | 編程 | 編程比賽 | 演算法與數據結構 |