tgoop.com/bminaiev_blog/48
Last Update:
Lazy Fenwick Tree
Чтобы канал не пустовал расскажу о простом трюке, который возможно не все знают. Допустим нам нужна структура данных, которая умеет поддерживать массив чисел a и обрабатывать две операции:+ l r x. Ко всем элементам на отрезке l..r добавить число x.? pos. Узнать значение элемента a[pos].
Это стандартная задача, которая решается деревом отрезков или деревом Фенвика. Обе структуры данных используют O(n) памяти, где n — размер массива a.
Что делать, если мы хотим обрабатывать такие же запросы, но для массива размером 10^9 элементов? Если все запросы известны заранее, то можно сжать координаты и свести задачу к предыдущей. А если нет, то можно написать Dynamic Segment Tree, в котором вершины дерева отрезков инициализируются в первый момент, когда к ним происходит обращение. Но в этом случае придется написать кода в несколько раз больше чем в обычном дереве Фенвика.
На самом деле можно все еще использовать дерево Фенвика, но хранить значения не в векторе, а в хеш таблице. Такая структура данных будет занимать O(Q * log(MAX_C)) памяти, где Q — количество запросов, а MAX_C — размер массива a. При этом код почти не отличается от обычного дерева Фенвика:
struct LazyFenwick {
data: FxHashMap<i32, i32>,
n: i32,
}
impl LazyFenwick {
pub fn get_sum(&self, mut pos: i32) -> i32 {
let mut res = 0;
loop {
res += self.data.get(&pos).copied().unwrap_or_default();
pos = pos & (pos + 1);
if pos == 0 {
return res;
}
pos -= 1;
}
}
pub fn add(&mut self, mut pos: i32, change: i32) {
while pos < self.n {
*self.data.entry(pos).or_default() += change;
pos |= pos + 1;
}
}
}
Другой подход, который я подсмотрел в https://contest.ucup.ac/submission/229077, написать bottom-up дерево отрезков, которое тоже хранит значения в хеш-таблице:ll N, Q;
unordered_map<ll, ll> seg;
void add(ll L, ll R, ll x) {
L += N; R += N;
for(; L < R; L >>= 1, R >>= 1) {
if(L & 1) seg[L++] += x;
if(R & 1) seg[--R] += x;
}
}
ll get(ll i) {
i += N;
ll ans = 0;
do ans += seg[i]; while(i >>= 1);
return ans;
}
BY Боря программирует
Share with your friend now:
tgoop.com/bminaiev_blog/48