Как я могу реализовать деревья сегментов с ленивым распространением?
Я реализую дерево сегментов, чтобы иметь возможность быстро отвечать на следующие запросы в массиве A:
- запрос i, j: сумма всех элементов в диапазоне (i,j)
- обновить i, j, k: добавить k ко всем элементам в диапазоне (i,j)
Вот моя реализация:
typedef long long intt;
const int max_num=100000,max_tree=4*max_num;
intt A[max_num],ST[max_tree];
void initialize(int node, int be, int en) {
if(be==en) {
ST[node]=ST[be];
} else {
initialize(2*node+1,be,(be+en)/2);
initialize(2*node+2,(be+en)/2+1,en);
ST[node]=ST[2*node+1]+ST[2*node+2];
}
}
void upg(int node, int be, int en, int i, intt k) {
if(be>i || en<i || be>en) return;
if(be==en) {
ST[node]+=k;
return;
}
upg(2*node+1, be, (be+en)/2, i, k);
upg(2*node+2, (be+en)/2+1, en, i, k);
ST[node] = ST[2*node+1]+ST[2*node+2];
}
intt query(int node, int be, int en, int i, int j) {
if(be>j || en<i) return -1;
if(be>=i && en<=j) return ST[node];
intt q1=query(2*node+1, be, (be+en)/2, i, j);
intt q2=query(2*node+2, (be+en)/2+1, en, i, j);
if(q1==-1) return q2;
else if(q2==-1) return q1;
else return q1+q2;
}
Функция запроса действительно быстрая, ее сложность O(lg N), где N - ji. Функция обновления также в среднем быстрая, но когда ji велико, сложность обновления составляет O(N lg N), что совсем не быстро.
Я немного искал предмет и обнаружил, что если я реализую дерево сегментов с ленивым распространением, сложность как запроса, так и обновления равна O(lg N), что асимптотически быстрее, чем O(N lg N).
Я также нашел ссылку на другой вопрос, который имеет действительно хорошую реализацию дерева сегментов, в котором используются указатели: Как реализовать деревья сегментов с ленивым распространением?, Итак, вот мой вопрос: существует ли более простой способ реализации отложенного распространения, без использования указателей, но с индексами массива и без segment_tree структура данных?
2 ответа
Это я играю с этой структурой данных и некоторыми шаблонными дураками.
В нижней части всего этого беспорядка находятся два плоских массива, один из которых содержит дерево сумм, а другой - дерево значений переноса, которые затем распространяются вниз. Концептуально они образуют одно двоичное дерево.
Истинное значение узла в двоичном дереве - это значение в хранимой сумме, плюс число листьев под узлом, умноженное на сумму всех значений дерева переноса от узла до корня.
В то же время истинное значение каждого узла в дереве равно истинному значению каждого конечного узла под ним.
Я написал одну функцию для выполнения переноса и суммирования, поскольку оказывается, что они посещают одни и те же узлы. И читал иногда пишет. Таким образом, вы получите сумму, позвонив с increase нуля.
Все, что делает шаблон tomfoolery, - это вычисление того, где смещения в каждом дереве находятся узлы и где находятся левый и правый дочерние элементы.
Хотя я использую struct, struct является переходным процессом - это просто оболочка с некоторыми предварительно вычисленными значениями вокруг смещения в массиве. Я храню указатель на начало массива, но каждый block_ptr использует точно такой же root Значение в этой программе.
Для отладки у меня есть несколько дурацких макросов Assert() и Debug(), а также нулевая функция трассировки, которую вызывает функция рекурсивного суммирования (которую я использую для отслеживания общего количества вызовов в нее). Еще раз, быть излишне сложным, чтобы избежать глобального состояния.:)
#include <memory>
#include <iostream>
// note that you need more than 2^30 space to fit this
enum {max_tier = 30};
typedef long long intt;
#define Assert(x) (!(x)?(std::cout << "ASSERT FAILED: (" << #x << ")\n"):(void*)0)
#define DEBUG(x)
template<size_t tier, size_t count=0>
struct block_ptr
{
enum {array_size = 1+block_ptr<tier-1>::array_size * 2};
enum {range_size = block_ptr<tier-1>::range_size * 2};
intt* root;
size_t offset;
size_t logical_offset;
explicit block_ptr( intt* start, size_t index, size_t logical_loc=0 ):root(start),offset(index), logical_offset(logical_loc) {}
intt& operator()() const
{
return root[offset];
}
block_ptr<tier-1> left() const
{
return block_ptr<tier-1>(root, offset+1, logical_offset);
}
block_ptr<tier-1> right() const
{
return block_ptr<tier-1>(root, offset+1+block_ptr<tier-1>::array_size, logical_offset+block_ptr<tier-1>::range_size);
}
enum {is_leaf=false};
};
template<>
struct block_ptr<0>
{
enum {array_size = 1};
enum {range_size = 1};
enum {is_leaf=true};
intt* root;
size_t offset;
size_t logical_offset;
explicit block_ptr( intt* start, size_t index, size_t logical_loc=0 ):root(start),offset(index), logical_offset(logical_loc)
{}
intt& operator()() const
{
return root[offset];
}
// exists only to make some of the below code easier:
block_ptr<0> left() const { Assert(false); return *this; }
block_ptr<0> right() const { Assert(false); return *this; }
};
template<size_t tier>
void propogate_carry( block_ptr<tier> values, block_ptr<tier> carry )
{
if (carry() != 0)
{
values() += carry() * block_ptr<tier>::range_size;
if (!block_ptr<tier>::is_leaf)
{
carry.left()() += carry();
carry.right()() += carry();
}
carry() = 0;
}
}
// sums the values from begin to end, but not including end!
// ie, the half-open interval [begin, end) in the tree
// if increase is non-zero, increases those values by that much
// before returning it
template<size_t tier, typename trace>
intt query_or_modify( block_ptr<tier> values, block_ptr<tier> carry, int begin, int end, int increase=0, trace const& tr = [](){} )
{
tr();
DEBUG(
std::cout << begin << " " << end << " " << increase << "\n";
if (increase)
{
std::cout << "Increasing " << end-begin << " elements by " << increase << " starting at " << begin+values.offset << "\n";
}
else
{
std::cout << "Totaling " << end-begin << " elements starting at " << begin+values.logical_offset << "\n";
}
)
if (end <= begin)
return 0;
size_t mid = block_ptr<tier>::range_size / 2;
DEBUG( std::cout << "[" << values.logical_offset << ";" << values.logical_offset+mid << ";" << values.logical_offset+block_ptr<tier>::range_size << "]\n"; )
// exatch math first:
bool bExact = (begin == 0 && end >= block_ptr<tier>::range_size);
if (block_ptr<tier>::is_leaf)
{
Assert(bExact);
}
bExact = bExact || block_ptr<tier>::is_leaf; // leaves are always exact
if (bExact)
{
carry()+=increase;
intt retval = (values()+carry()*block_ptr<tier>::range_size);
DEBUG( std::cout << "Exact sum is " << retval << "\n"; )
return retval;
}
// we don't have an exact match. Apply the carry and pass it down to children:
propogate_carry(values, carry);
values() += increase * end-begin;
// Now delegate to children:
if (begin >= mid)
{
DEBUG( std::cout << "Right:"; )
intt retval = query_or_modify( values.right(), carry.right(), begin-mid, end-mid, increase, tr );
DEBUG( std::cout << "Right sum is " << retval << "\n"; )
return retval;
}
else if (end <= mid)
{
DEBUG( std::cout << "Left:"; )
intt retval = query_or_modify( values.left(), carry.left(), begin, end, increase, tr );
DEBUG( std::cout << "Left sum is " << retval << "\n"; )
return retval;
}
else
{
DEBUG( std::cout << "Left:"; )
intt left = query_or_modify( values.left(), carry.left(), begin, mid, increase, tr );
DEBUG( std::cout << "Right:"; )
intt right = query_or_modify( values.right(), carry.right(), 0, end-mid, increase, tr );
DEBUG( std::cout << "Right sum is " << left << " and left sum is " << right << "\n"; )
return left+right;
}
}
Вот несколько вспомогательных классов, которые упрощают создание дерева сегментов заданного размера. Обратите внимание, однако, что все, что вам нужно, это массив правильного размера, и вы можете создать block_ptr из указателя на элемент 0, и вы готовы к работе.
template<size_t tier>
struct segment_tree
{
typedef block_ptr<tier> full_block_ptr;
intt block[full_block_ptr::range_size];
full_block_ptr root() { return full_block_ptr(&block[0],0); }
void init()
{
std::fill_n( &block[0], size_t(full_block_ptr::range_size), 0 );
}
};
template<size_t entries, size_t starting=0>
struct required_tier
{
enum{ tier =
block_ptr<starting>::array_size >= entries
?starting
:required_tier<entries, starting+1>::tier
};
enum{ error =
block_ptr<starting>::array_size >= entries
?false
:required_tier<entries, starting+1>::error
};
};
// max 2^30, to limit template generation.
template<size_t entries>
struct required_tier<entries, size_t(max_tier)>
{
enum{ tier = 0 };
enum{ error = true };
};
// really, these just exist to create an array of the correct size
typedef required_tier< 1000000 > how_big;
enum {tier = how_big::tier};
int main()
{
segment_tree<tier> values;
segment_tree<tier> increments;
Assert(!how_big::error); // can be a static assert -- fails if the enum of max tier is too small for the number of entries you want
values.init();
increments.init();
auto value_root = values.root();
auto carry_root = increments.root();
size_t count = 0;
auto tracer = [&count](){count++;};
intt zero = query_or_modify( value_root, carry_root, 0, 100000, 0, tracer );
std::cout << "zero is " << zero << " in " << count << " steps\n";
count = 0;
Assert( zero == 0 );
intt test2 = query_or_modify( value_root, carry_root, 0, 100, 10, tracer ); // increase everything from 0 to 100 by 10
Assert(test2 == 1000);
std::cout << "test2 is " << test2 << " in " << count << " steps \n";
count = 0;
intt test3 = query_or_modify( value_root, carry_root, 1, 1000, 0, tracer );
Assert(test3 == 990);
std::cout << "test3 is " << test3 << " in " << count << " steps\n";
count = 0;
intt test4 = query_or_modify( value_root, carry_root, 50, 5000, 87, tracer );
Assert(test4 == 10*(100-50) + 87*(5000-50) );
std::cout << "test4 is " << test4 << " in " << count << " steps\n";
count = 0;
}
Хотя это не тот ответ, который вам нужен, кто-то может облегчить его написание. И написание этого позабавило меня. Так что, надеюсь, это поможет!
Код был протестирован и скомпилирован на Ideone.com с использованием компилятора C++0x.
Ленивое распространение означает обновление только при необходимости. Это метод, который позволяет выполнять обновления диапазона с асимптотической сложностью времени O(logN) (N здесь - это диапазон).
Скажем, вы хотите обновить диапазон [0,15], затем вы обновляете узлы [0,15] и устанавливаете флаг в узле, который говорит, что его дочерние узлы должны быть обновлены (используйте значение Sentinel, если флаг не используемый).
Возможный стресс-тест:
0 1 100000
0 1 100000
0 1 100000... повторите Q раз (где Q = 99999) и 100000-й запрос будет
1 1 100000
В этом случае большинство вложений будет стоить, переворачивая 100000 монет 99999 раз, просто чтобы ответить на один простой запрос в конце и время ожидания.
При ленивом распространении вам просто нужно перевернуть узел [0,100000] 99999 раз и установить / снять флаг, что его дочерние элементы должны быть обновлены. Когда запрашивается сам фактический запрос, вы начинаете обходить его дочерние элементы и начинаете переключать их, нажимаете флаг вниз и снимаете флажок родительского элемента.
Да, и убедитесь, что вы используете правильные процедуры ввода / вывода (scanf и printf вместо cin и cout, если это C++). Надеюсь, это дало вам представление о том, что означает ленивое распространение. Дополнительная информация: http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296