Логин: Пароль:

Спортивное программирование
в Красноярском крае


k_mihey
kormyshov


 


Перейти к профилю
Вернуться к ленте

И снова дерево Фенвика

Многие знают мою любовь к этой структуре данных за её изящество и скорость. Рассказываю её всем своим ученикам. К сожалению её применение несколько ограничено (и применяемыми функциями, и интервальными обновлениями).

Дима Семак уже выкладывал мою реализацию модификации дерева Фенвика для функций min/max. Сегодня я расширил рамки применения и представляю вам модификацию с обновлением на отрезке.

Здесь выложу лишь код, вдруг кто-нибудь захочет протестировать или соптимизировать. А с пояснениями готовлю пост на Хабр. Сам замеры скорости пока не проводил, но решение задачи С с последнего codeforces-раунда работает 218мс против 406мс для RSQ.

class fenwick_add{
    int *m, N, *mt;
public:
    fenwick_add(int n){
        N = n;
        m = new int[N];
        mt = new int[N];
        memset(m, 0, sizeof(int)*N);
        memset(mt, 0, sizeof(int)*N);
    }
    void add(int i, int d){
        for(;i<N;i|=i+1) m[i] += d;
    }
    void add_range(int r, int d){
        if(r<0) return ;
        for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d;
        for(int i=r|(r+1);i<N;i|=i+1) m[i] += d*(r-(i&(i+1))+1);
    }
    void add_range(int l, int r, int d){
        add_range(r, d);
        add_range(l-1, -d);
    }
    int sum(int r){
        if(r<0) return 0;
        int res = 0;
        for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1);
        for(int i=r|(r+1);i<N;i|=i+1) res += mt[i]*(r-(i&(i+1))+1);
        return res;
    }
    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }

2013-02-27


2013-02-27 kormyshov
Пацаны, я ещё и инициализацию за O(N) сделал. RSQ в топку :-)

2013-02-27 kormyshov
А вот и ссылка на Хабр: http://habrahabr.ru/post/170933/

2013-03-02 vmgurov
круто. +1

2013-03-03 demidenko
а дерево отрезков специально как попало написал? а то у меня за 296 работает

2013-03-03 demidenko
а, стоп, я другое писал:) прибавление, но без суммы. но всё равно, например рекурсивный init и 4*N это плохо

2013-03-03 kormyshov
Всё равно у тебя памяти будет 2*3*N против 2*N. С init'ом согласен, но для Хабра надо было какое-то сравнение, а е-махх более менее известен.

Система Orphus

(c) Copyright 2011-2014 Михаил Кормышов

kormyshov[dog]gmail.com