LISとFenwick Tree - でも今日はSRMあるから

概要

Longest increasing subsequence 問題はFenwick treeを用いてO(n log m)で解ける（nは列の長さ、mは要素の最大値）
実行時間としては二分探索を用いる方法と大きな差はない

動機

今朝のCodeforces Round #468の他人のコードを見るとLISをFenwick treeで解いている。それも考察の結果で偶然FenwickになったわけではなくLISはFenwickで解くという強い意志を感じる。実際それで1位を取っている。調べるとCodeforcesの記事やGeeksforGeeksの解説がヒットする。つまりこの手法は常識であり、これを知らないままプログラミングコンテストをやっていたのは舐めプだ。

LIS

長さnの数列a[0], ..., a[n-1]が与えられる。数列から0個以上n個以下の要素を消去してできた数列a'[0], ..., a'[k-1]がa'[i] < a'[i+1]を満たすとき、a'を増加部分列と呼ぶ。最長の増加部分列の長さを出力せよ。
1 <= n <= 10^5
1 <= a[i] <= 10^5
a[i]は整数

二分探索による解法

プログラミングコンテストチャレンジブックやWikipediaに載っている。

int buf[MAX_N];
void lis() {
    const int INF = 1<<30;
    for (int i=0; i<N; i++) buf[i] = INF;
    for (int i=0; i<N; i++) *lower_bound(buf, buf+N, A[i]) = A[i];
    int len = lower_bound(buf, buf+N, INF) - buf;
    printf("%d\n", len);
}

INFはa[i]より大きい値であればよい。INFを定義したくない、または初期化をしたくないなら次のコードもよい。

int buf[MAX_N];
void lis() {
    int len = 0;
    for (int i=0; i<N; i++) {
	int k = lower_bound(buf, buf+len, A[i]) - buf;
	buf[k] = A[i];
	if (len == k) len++;
    }
    printf("%d\n", len);
}

Fenwick treeによる解法

Fenwick treeは最大値を出力するクエリの場合

更新はincremental。つまり、より大きい値の更新が来た場合だけ書き換える
出力質問の範囲はprefixのみ

2つの制約が付くがこれでよい。

const int SIZE = MAX_A + 1;
int buf[SIZE];

void update(int i, int x) {
    for (; i<SIZE; i|=i+1) buf[i] = max(buf[i], x);
}

int get_max(int r) {
    int ret = 0;
    for (; r; r&=r-1) ret = max(ret, buf[r-1]);
    return ret;
}

void lis() {
    for (int i=0; i<SIZE; i++) buf[i] = 0;
    for (int i=0; i<N; i++) {
	int k = get_max(A[i]);
	update(A[i], k+1);
    }
    int len = get_max(SIZE);
    printf("%d\n", len);
}

比較

よくある問題設定ならば実行時間はどれも大差ない。しかしa[i]の最大値制約が強い場合（100程度）はFenwick treeの解法が2倍以上速い。
逆に、a[i]の制約が緩い（10^9程度）場合や、a[i]がint型以外の場合は前処理でa[i]を0~n-1に写像しなければならず、やや面倒であり、オンライン問題には使いづらい。