Содержание
- 3. The Basic idea of a segment tree
- 4. Рассмотрим пример реализации дерева отрезков для следующих запросов: 1) Добавить к i-му элементу значение d 2)
- 5. Creating structure struct Tree { vector t; int size; };
- 6. Initialization of the tree void init(vector &a){ size = 1; while(size t.resize(2 * size, 0); //0
- 7. The change request void change(int v, int tl, int tr, int i, int d){ if (tl
- 8. Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l >
- 9. Let’s make the task more difficult Запросы: 1) Изменить значение элементов [l;r] на d 2) Получить
- 10. struct Tree { vector t; vector add // array for method of “lazy propagation” int size;
- 11. The main function of the method void push(int v){ add[2*v]+= add[v]; add[2*v+1]+= add[v]; add[v] = 0;
- 12. The change request void change(int v, int tl, int tr, int l, int r, int d){
- 13. Getting sum int sum(int v, int tl, int tr, int l, int r){ if (l >
- 15. Скачать презентацию