1 Тема от Senya Отредактировано Senya (2010-10-10 21:26:38)

  • Senya
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-01
  • Сообщений: 11

Тема: Дерево отрезков - память

Хм. помоему не 4n а 2n-1 вершин должно быть. все вершины кроме листьев - разделяют элементы - их столько же сколько можно поставить перегородок между n элементами = n-1. ну и плюс листья - n штук. если еще для удобства добавить нулевой элемент - будет 2n.
Более того опыт показывает (http://e-maxx.ru/algo/segment_tree - скопировал просто отсюда код и потестил) что половина массива t - нули. даже если n = (2^k)+1. получается не полное двоичное дерево.. в чем нет ничего плохого при такой реализации (если делим пополам массив нечетной длины то "большая половина" будет левой частью).

2 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: Дерево отрезков - память

4n действительно грубовато но и 2n мало.
тут надо 2 * (min k такое что 2^k >= n)

например для стандартного N <= 100000 хватит
int t[1 << 18]

А вообще пора http://e-maxx.ru/algo/segment_tree переписывать smile Когда дерево выровнено по 2^k все намного удобнее - можно легко определить за какой сегмент t[ i ] отвечает, легче делать Update и Build - без рекурсии.

Вот мой шаблон:

template <class T>
struct SegmentTree
{
    SegmentTree(const T* begin, const T* end)
    {        
        int sz = end - begin;
        Create(sz);

        copy(begin, end, values + dx);

        for (int i = dx - 1; i >= 1; i--)
        {
            values[i] = values[i * 2] + values[i * 2 + 1];
        }
    }

    SegmentTree(int sz)
    {
        Create(sz);
    }

    void Create(int sz)
    {
        dx = 1;
        while (dx < sz)
            dx *= 2;

        values = new T[dx * 2];
        memset(values, 0, sizeof(T) * dx * 2);
    }

    ~SegmentTree()
    {
        delete[] values;
    }

    void Update(int pos, T value)
    {
        pos += dx;
        values[pos] = value; 
        while (pos > 1)
        {
            pos /= 2;
            values[pos] = values[pos * 2] + values[pos * 2 + 1];
        }
    }
    
    T GetSegment(int l, int r, int pos, int tl, int tr)
    {
        if (l == tl && r == tr)
            return values[pos];
        int m = (tl + tr) / 2;
        if (r <= m)
            return GetSegment (l, r, pos * 2, tl, m);
        if (l >= m)
            return GetSegment (l, r, pos * 2 + 1, m, tr);

        return GetSegment (l, m, pos * 2, tl, m) + GetSegment (m, r, pos * 2 + 1, m, tr);
    }

    T GetSegment(int l, int r)
    {
        return GetSegment(l, r, 1, 0, dx);
    }

    T* values;    
    int dx;
};
    int a[] = {1,2,3,4};
    SegmentTree<int> tree(a, a + 4);
    int res = tree.GetSegment(0, 4); // r - как и в stl указывает на следующий за последним.

3 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Дерево отрезков - память

Вообще можно и простые запросы делать без рекурсии (пример для прибавления константы в точке и нахождения максимума на отрезке [l,r]):

const int MX=1<<17;
int mx[MX*2];
inline void update(int l,int a)
{
    l+=MX;
    for (mx[l]=a;l>>=1;) mx[l]=max(mx[l*2],mx[l*2+1]);
}
inline int fnd(int l,int r)
{
    int ans=-INF;
    for (l+=MX,r+=MX;l<=r;l=(l+1)/2,r=(r-1)/2) ans=max(ans,max(mx[l],mx[r]));
    return ans;
}