Боря программирует@bminaiev

Боря программирует

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;
}

www.tgoop.com/bminaiev_blog/48

2.7K viewsNov 4, 2023 at 13:12

tgoop.com/bminaiev_blog/48

Create: 2023-11-04
Last Update: 2025-05-05 18:54:26

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;
        }
    }
}

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

Telegram News

Lazy Fenwick Tree