метод построения дерева сегментов

Привет, я изучаю дерево сегментов. Построение дерева отрезков рекурсивным методом мне понятно, я реализовал его так:

void build( int n, int b, int e){
    if(b > e) return;
    else if (b == e) { tree[n] = arr[b]; return }
    build(n*2 , b , (b+e)/2 );
    build(n*2+1 , (b+e)/2+1 , e );
    tree[n] =  tree[n*2] + tree[n*2 + 1] ;
}

но я видел такую ​​​​реализацию шутера:

    void build() {  // build the tree
      for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
   }

i understand that t[i<<1] is same as  t[2*i] and t[i<<1|1] is same as t[2*i+1]

но как эта логика помогает мне построить дерево сегментов?? простой пример был бы очень полезен


c++ segment-tree
person kshitij singh    schedule 22.02.2016    source источник
comment
Вы можете показать полный исходный код короткой реализации? Я думаю, что функция build () строит только другой узел, кроме выхода, поэтому отпуск инициирован   -  person malioboro    schedule 22.02.2016
comment
@malioboro вот ссылка: ideone.com/0K8XPI и вот объяснение, которое я искал: codeforces.com/blog/entry/18051   -  person kshitij singh    schedule 23.02.2016

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле в вашем коде и их коде есть другая «функция» build(). В вашем коде, когда вы строите дерево сегментов, вы также вводите значение листьев, но в своем коде они вводят значение листьев в этом выражении:

for (int i = 0; i < n; ++i) scanf("%d", t + n + i);

и используйте build() только для заполнения другого узла

person malioboro    schedule 23.02.2016
comment
спасибо большое я понял. Но как приведенный выше оператор заполняет узлы выхода. Я имею в виду, как работает вышеуказанный scanf()? - person kshitij singh; 23.02.2016
comment
он использует концепцию указателя, просто сказал scanf("%d", t + n + i) то же самое с scanf("%d", &t[n+i]) - person malioboro; 23.02.2016