1

Тема: Дерево отрезков (изменение на отрезке)

Мне кажется, что в статье про дерево отрезков, а именно в разделе про изменение на отрезке что-то недосказано.

А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[ i ] новое значение, которое мы хотим записать.

А если не совпали? Видимо, надо посмотреть, стоит ли в данной вершине Val [ i ], и если стоит, то снять и раздать детям (всё-таки, это не так очевидно ;) ).

Re: Дерево отрезков (изменение на отрезке)

Да. В дополнительном массиве можно использовать два зарезервированных значения. Первое - взять значение из суммы на отрезке [l,r], второе - продолжать спуск ниже.

struct segment_tree
{
    int n;
    std::vector<int> data;
    std::vector<int> values;
    std::vector<int> etalon;

    segment_tree(const std::vector<int>& array)
    {
        etalon = array; // DEBUG

        n = 1;
        while(n < (int)array.size())
            n <<= 1;

        data.assign(2*n, 0);
        values.assign(2*n, 0);

        for(int i = 0; i < (int)array.size(); ++i)
            data[i+n] = array[i];

        for(int i = n-1; i > 0; --i)
            data[i] = data[2*i] + data[2*i+1];
    }

    void test(int block)
    {
        std::cout << "Running Test Block #" << block << "\n\n";

        int t = 0;
        for(int i = 0; i < (int)etalon.size();++i)
        {
            for(int j = i; j < (int)etalon.size(); ++j)
            {
                t++;

                int sum = get_sum(i,j), sum_etalon = get_sum_etalon(i, j);

                char buf[0xff]={0};
                sprintf(buf, "%02d", t);
                if (sum != sum_etalon)
                    std::cout << "Test #" << buf << " FAILED!\n";
                else
                    std::cout << "Test #" << buf << " PASSED!\n";

            }
        }

        std::cout << "\n";
    }

    int get_sum_etalon(int l, int r)
    {
        int sum_etalon = 0;
        for(int k = l; k <= r; ++k)
            sum_etalon += etalon[k];

        return sum_etalon;
    }

    int get_sum(int l, int r)
    {
        return get_sum(1, 0, n-1, l, r);
    }

    int get_sum(int root, int left, int right, int l, int r)
    {
        if (values[root] > 0)
            return values[root]*(r-l+1);

        if (l == left && r == right && values[root] != -1)
            return data[root];

        int sum = 0;

        int right_dash = (right+left)/2, left_dash = (right+left)/2+1;
        if (l <= right_dash)
            sum += get_sum(root*2, left, right_dash, l, std::min<int>(r, right_dash) );

        if (r >= left_dash)
            sum += get_sum(root*2+1, left_dash, right, std::max<int>(left_dash, l), r);

        return sum;
    }

    void set_value(int l, int r, int value)
    {
        set_value_etalon(l, r, value);
        set_value(1, 0, n-1, l, r, value);
    }

    void set_value_etalon(int l, int r, int value)
    {
        for(int k = l; k <= r; ++k)
            etalon[k] = value;
    }

    void set_value(int root, int left, int right, int l, int r, int value)
    {
        if (l == left && r == right)
        {
            values[root] = value;
            return;
        }

        if (values[root] > 0)
            values[root*2 + 1] = values[root*2] = values[root];
        
        values[root] = -1;

        int right_dash = (right+left)/2, left_dash = (right+left)/2+1;
        if (l <= right_dash)
            set_value(root*2, left, right_dash, l, std::min<int>(r, right_dash), value);

        if (r >= left_dash)
            set_value(root*2+1, left_dash, right, std::max<int>(left_dash, l), r, value);
    }
};


int main(int argc, char* argv[])
{
    int data[] = {1,2,3,4,5,6,7,8,9};
    std::vector<int> arr(data, data+sizeof(data)/sizeof(data[0]));
    segment_tree st(arr);

    int t = 1;
    st.test(t++);

    st.set_value(0, 6, 4);
    st.test(t++);

    st.set_value(1, 4, 6);
    st.test(t++);

    st.set_value(2, 8, 5);
    st.test(t++);

}

3

Re: Дерево отрезков (изменение на отрезке)

Кстати, мне не очень понятно, почему размер массива должен быть в 4 раза больше количества элементов. Ведь, кажется, из самого построения алгоритма видно, что вершин в дереве 2n - 1. В чем я неправ?

Re: Дерево отрезков (изменение на отрезке)

vanla пишет:

Кстати, мне не очень понятно, почему размер массива должен быть в 4 раза больше количества элементов. Ведь, кажется, из самого построения алгоритма видно, что вершин в дереве 2n - 1. В чем я неправ?

В лучшем случае будет нужно 2n-1 памяти -- когда размер исходного массива степень двойки, вот представьте полное бинарное дерево, и посчитайте сколько оно будет занимать памяти. Если же размер не степень двойки, то размер исходного массива дополняют до степени -- отсюда и такая оценка.

5

Re: Дерево отрезков (изменение на отрезке)

В новой версии статьи постарался покрыть все эти вопросы. Жду ещё конструктивных замечаний smile

6

Re: Дерево отрезков (изменение на отрезке)

Есть небольшие сомнения в тех частях, где рассказывается про поиск подотрезка с максимальной суммой, и где говорится о двумерных деревьях. Вообще все коды я тестировал только вручную, не отсылал никуда, поэтому есть некоторая вероятность ошибки.