題目放這裡～

• TIOJ 1080
• ZJ d799
• ATC DPcontest PQ
• TIOJ 1869
• Codechef SUBARR

樹狀數組

• 支援：單點加值，前綴和（時間複雜度
  $O(logn)$ ）
• 空間複雜度：
  $O(n)$

const int MAXN;
int BIT[MAXN+5];

//單點加值
void add(int k, int val){
    while(k <= MAXN){
        BIT[k] += val;
        k += (k&-k);
    }
}

//前綴和
int sum(int k){
    int ret = 0;
    while(k){
        ret += BIT[k];
        k -= (k&-k);
    }
    return ret;
}

離散化

• 當只在乎序列中的大小關係的時候，可以使用離散化，縮小數值範圍
• 其實就是排序＋編碼

講講 ZJ d799

• ZJ d799
  原本數列：
  $a_1,a_2,a_3,...,a_n$
  ＝>
  $a_1-0,a_2-a_1,a_3-a_2,a_4-a_3,...$
  差分數列：
  $d_1,d_2,d_3,d_4...$
• 區間修改，單點求值：
  • 對差分數列建 BIT
  • 修改：
    $[a_3,a_7]$ 都加上
    $k$
    • $d_3=a_3-a_2+=k$
    • $d_8=a_8-a_7-=k$
  • 求值：
    $a_i=\sum _1^j{d}_j$
• 區間修改，區間和：
  • 區間和：
    $[a_3,a_7]$ 的區間和
    • $\sum _3^7{a}_i=\sum _3^7\sum _1^j{d}_j$
    • $=d_1\ast 5+d_2\ast 5+d_3\ast 5+d_4\ast 4+d_5\ast 3+d_6\ast 2+d_7\ast 1$
    • $=(d_1+d_2+d_3+d_4+d_5+d_6+d_7)\ast 5-(d_4\ast 1+d_5\ast 2+d_6\ast 3+d_7\ast 4)$
    • $a_3=(d_1+d_2+d_3)$
    • $a_4=(d_1+d_2+d_3+d_4)$
    • $a_5=(d_1+d_2+d_3+d_4+d_5)$
    • $a_6=(d_1+d_2+d_3+d_4+d_5+d_6)$
    • $a_7=(d_1+d_2+d_3+d_4+d_5+d_6+d_7)$
  • 再建一個BIT：
    • $d_1\ast 1,d_2\ast 2,d_3\ast 3,...$
  • 區間和：
    • $=(d_1+d_2+d_3)\ast 5+(d_4+d_5+d_6+d_7)\ast 8-(d_4\ast 4+d_5\ast 5+d_6\ast 6+d_7\ast 7)$