Дерево двоичного индекса (обновление диапазона и точечный запрос)

Question

Может ли кто-нибудь помочь мне понять в дереве двоичного индекса, когда мы делаем обновление диапазона - Почему нет, мы обновляем каждый элемент, почему только начальный элемент и конечный элемент

Например 0

мы должны обновить диапазон элементов массива в BIT для arr[x] до arr[y] . В соответствии с функцией обновления точки дерева двоичных индексов. Она обновит совокупную частоту индекса x и всех тех индексов> чем x, которые будут получены при обновлении,

---

Но если мы используем функцию обновления точки для обновления диапазона. Поэтому мы не обновляем каждый индекс больше, чем x и меньше, чем y, используя функцию обновления точки. Поскольку значение "обновление диапазона" означает, что каждый элемент должен обновляться со значением и как обновление начального индекса и одного указанного выше конечного индекса охватывает все обновления

почему мы не делаем

..................................................

 for (i =[x] to [y])
    pointupdate(ar[i],val);// why we are not doing this 

update(p, v): //point update
  for (; p <= N; p += p&(-p))
    ft[p] += v   

# Add v to A[a...b] 
update(a, b, v):     // why we are using this only for update of one element how other elements greater than a will be coverd
  update(a, v)     
  update(b + 1, -v)     

я

Answer 1

Когда вы обновляете BIT[a]+=v, это означает, что запрос по каждому индексу x>=a увидим v приращение.

Чтобы выполнить обновление диапазона таким образом, вы увеличиваете v на диапазоне начинается и уменьшается v после окончания диапазона. Это значит только между a а также b приращение будет видно.