В последнем последнем руководстве мы узнали, как построить дерево сегментов, запросить его и обновить в нем значения точек. В этом руководстве мы изучим полезную технику Ленивое распространение для деревьев сегментов. Используя ленивое распространение, мы можем эффективно обновлять диапазон в дереве. В этом методе мы обновляем значение ленивым образом, поскольку название напрашивается само. Из-за ленивости значения не обновляются без необходимости. Следовательно, «ленивое распространение» примерно означает «ленивое» распространение значений из корневого каталога.
Поясним на примере. Предположим, мы построили дерево сегментов, и в нем доступны два типа запросов. Первый - это обновление, которое добавляет некоторое значение узлам в определенном диапазоне. Второй тип - это запрос суммы, который запрашивает сумму значений узлов для заданного диапазона. В ленивом распространении термин «ленивый» относится к идее, что мы не будем обновлять диапазон вплоть до конечных узлов при каждом его вызове. Поскольку запрос суммы вызывается последним, мы будем накапливать значения в другом массиве каждый раз, когда вызывается update (), и эти накопленные значения будут предоставлять сумму только для запроса, который запрашивает сумму в диапазоне. Давайте рассмотрим пример, чтобы прояснить концепцию.
Вопрос
Вам дается массив из N элементов, которые изначально равны нулю. После этого вам будут даны команды C. Это:
* 0 p q v - вам нужно добавить v ко всем числам в диапазоне от p до q (включительно), где p и q - два индекса массива.
* 1 p q - вывести строку, содержащую одно целое число, которое является суммой всех элементов массива между p и q (включительно)
Ввод:
В первой строке вы увидите T, количество тестов.
Каждый тестовый пример начинается с N (N ‹= 100 000) и C (C‹ = 100 000). После этого вам будут предоставлены команды C в указанном выше формате. 1 ‹= p, q‹ = N и 1 ‹= v‹ = 10⁷.
Вывод:
Распечатайте ответы на вопросы.
Источник вопроса: SPOJ - УЖАСНО
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.FileInputStream;
class lazypropagation {
long tree[]; //the Segment tree
long helper[]; //this array accumulates value to be updated
//if true, values are pending for this node to be updated
boolean flag[];
lazypropagation(){
tree = new long [262145];
helper = new long [262145];
flag = new boolean [262145];
//initialize all node of tree and helper with zero
Arrays.fill (tree, 0);
Arrays.fill (helper, 0);
//initially set all flags to false as their is no pending value for any node
Arrays.fill (flag, false);
}
/**
* @param nodeToUpdate node in tree to be updated
* @param valueToUpdate value to be updated
* @param left is beginning index of array
* @param right is ending index of array
* @param start is beginning index of query
* @param end is ending index of query
**/
private void update (int node, int value, int left, int right, int start, int end){
/**
* Legends:
* S = Start, E = End, L = Left, R = Right
* dotted lines ---- represents array
* square brackets [ ] denote range of query
*
**/
// When range to be updated does not intersect
// with the array indices [left, right]
// ...E] L------R [S...
if ( end <left || start > right )
return ;
// left == right means we've reached to a single element of array.
if (left == right ){
tree[node]+= value;
//flag is true mean some value is pending in helper[node]
//so we should add this to tree[node] and clear helper[node]
if (flag[node]==true){
tree[node] += helper[node];
helper[node]=0;
}
return;
}
int leftChild = 2*node;
int rightChild = 2*node + 1;
//Each of the below case finds a range by right-left+1 or end-left+1
//this range should be multiplied by value and should be added to tree[node]
// [S L------R E]
if (start <= left && right <= end){
helper[leftChild] += value;
helper[rightChild] += value;
flag[leftChild] = flag[rightChild] = true;
tree[node] += (value *(right - left +1));
return ;
}
// ---[S---R E]
else if (start <= right && right < end)
tree[node ] += (value*(right - start +1));
// [S L----E]----
else if (start < left && left <= end )
tree[node] += (value*(end - left + 1));
// ----L----[S-----E]-----R-----
else if (left <= start && end <= right)
tree[node] += (value*(end - start + 1));
update (leftChild, value, left, (left+right)/2, start, end );
update (rightChild, value, ((left+right)/2)+1, right, start, end);
}
private long sum_of_range (int node, int left, int right, int start, int end){
// query does not overlaps with array range
// ---R---- [S E]----L-----
if (right < start || end < left)
return 0;
int leftChild = 2*node;
int rightChild = 2*node+1;
// true means value updates are pending for the node
if (flag[node] == true){
//update value in tree node
// right-left+1 gives the range for which
//values to be updated in parent node which here is tree[node]
tree[node] += (helper[node] *(right-left+1));
//after values are updated, set flag to false
flag[node]=false;
// if it's not a leaf node
if (left != right){
//push the flag downward to children of node because
//after recursive call these children will act as parent
//and then tree[node] would be calculated
flag [ leftChild ] = flag [ rightChild ] = true;
//push down the parent value to leftChild and rightChild
//hence updated values for child nodes would be the sum of their own values + parent node value
helper[ leftChild ] += helper[node];
helper[ rightChild ] += helper[node];
}
//as value of helper[node] is already added to its children
// set helper[node] = 0 to receive fresh values
helper[node]=0;
}
// return value of tree[node] as query completely overlaps the array range
// hence no need to go further on its children nodes.
// [S---L---R---E]
if (start <= left && right <= end){
return tree[node];
}
//sum returned for left half of tree intersecting with query
long s1 = sum_of_range(leftChild, left, (left+right)/2, start, end);
//sum returned for right half of tree intersecting with query
long s2 = sum_of_range(rightChild, ((left+right)/2)+1, right, start, end);
return s1+s2;
}
public static void main (String [] args) throws IOException{
// for reading input from console use new InputStreamReader (System.in)
BufferedReader br = new BufferedReader (new InputStreamReader (new FileInputStream("input.txt")));
StringTokenizer st =null;
int t = Integer.parseInt(br.readLine());
for(;t>0;t--){
st = new StringTokenizer (br.readLine());
int N = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
lazypropagation segtree = new lazypropagation();
for (int I=1;I<=C;I++){
st = new StringTokenizer(br.readLine());
if (st.nextToken().equals("0")){
int P = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
segtree.update (1, V, 1, N, P,Q);
}
else {
int P = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
long ans = segtree.sum_of_range (1,1,N, P,Q);
System.out.println(ans);
}
}
}
}
}
В приведенном выше коде update () отвечает как за построение дерева, так и за обновление значений в нем. В update () мы взяли индексы массива слева от 1 и справа до N, поскольку N - это количество элементов в массиве. Существует четыре возможных случая пересечения диапазона массива и диапазона запроса. Все эти случаи представлены в комментариях update (). Основная идея update () состоит в том, чтобы накапливать обновляемое значение для тех узлов, которые являются пересечением диапазона запроса и диапазона массива в helper [node]. Эти значения будут накапливаться для каждого update () и будут обрабатываться при вызове sum_of_range (). Я добавил много комментариев в код, чтобы он не требовал пояснений. Тем не менее, если возникнут сомнения, оставьте комментарий. Спасибо за чтение. Хорошего дня!!!
