Как посчитать длину наибольшей возрастающей подпоследовательности (НВП/LIS) через дерево Фенвика по префиксному максимуму?
Знаю LIS за O(n log n) через бинпоиск по «хвостам» (patience sorting). Но в задаче нужна модификация — учитывать значения и считать число LIS, и там удобнее DP. Слышал, что LIS можно получить Фенвиком, который держит префиксный максимум длины. Как это устроено?
2 ответа
Идея: dp[i] — длина LIS, заканчивающейся в a[i], тогда dp[i] = 1 + max(dp[j]) по всем j<i с a[j] < a[i]. Этот «макс по меньшим значениям слева» считает Фенвик префиксного максимума по сжатым значениям: в позиции (ранг) значения храним лучшую достигнутую длину.
Но у max нет обратной операции, поэтому BIT тут работает только на префиксный max c обновлением «увеличить значение в точке» — а нам ровно это и нужно: запрос max по рангам < rank(a[i]) и обновление в rank(a[i]).
struct BITMax {
int n; vector<int> t;
BITMax(int n): n(n), t(n+1, 0) {}
void update(int i, int v){ for(; i<=n; i+=i&-i) t[i]=max(t[i], v); }
int query(int i){ int r=0; for(; i>0; i-=i&-i) r=max(r, t[i]); return r; }
};
int lis(vector<int> a){
vector<int> s(a); sort(s.begin(),s.end());
s.erase(unique(s.begin(),s.end()), s.end());
auto rank=[&](int x){ return int(lower_bound(s.begin(),s.end(),x)-s.begin())+1; };
BITMax bit((int)s.size());
int best=0;
for(int x: a){
int r=rank(x);
int len=bit.query(r-1)+1; // лучший среди строго меньших + сам x
bit.update(r, len);
best=max(best, len);
}
return best;
}
Сложность — O(n log n) время (сжатие + n запросов/обновлений), O(n) память. query(r-1) берёт максимум строго по меньшим значениям — это даёт строго возрастающую LIS. Для неубывающей замените на query(r) с аккуратной обработкой равных.
Почему именно Фенвик, а не бинпоиск по хвостам: версия с хвостами даёт только длину и плохо обобщается. А BIT-подход легко расширяется — например, считать число LIS максимальной длины: храните в узле пару (лучшая длина, количество способов) и при update объединяйте по правилу «при равной длине складываем счётчики, при большей — заменяем». Бинпоиском это уже не выразить. Так что для «LIS + что-то ещё» берите Фенвик; для голой длины проще классический O(n log n) по хвостам. И помните: префиксный max в BIT — допустимый частный случай именно потому, что обновление только «увеличивает» и запрос только префиксный.