Тема: дерево отрезков
как можно с помощью дерева отрезков делать update(l,r,x) за O(logN)?
update(l, r, x) = обновить все элементы с l до r на x
Re: дерево отрезков
Обновить - в плане увеличить или сделать равными икс?
Если увеличить, то для каждого отрезка нужно помимо минимума хранить еще на сколько мы все числа из отрезка увеличивали. Обновление будет выглядеть примерно так:
void update(int l,int r,int a,int b,int val,int num)
{
if (l==a && b==r-1)
{
mod[num]+=val;
return;
}
int xx=(r+l)/2;
if (b<xx) update(l,xx,a,b,val,num*2); else
if (a>=xx) update(xx,r,a,b,val,num*2+1); else
{
update(l,xx,a,xx-1,val,num*2);
update(xx,r,xx,b,val,num*2+1);
}
mn[num]=min(mn[num*2]+mod[num*2],mn[num*2+1]+mod[num*2+1]);
}Поиск минимума так:
ll fnd(int l,int r,int a,int b,int num)
{
if (l==a && b==r-1) return mn[num]+mod[num];
int xx=(r+l)/2;
if (b<xx) return fnd(l,xx,a,b,num*2)+mod[num]; else
if (a>=xx) return fnd(xx,r,a,b,num*2+1)+mod[num]; else
return min(fnd(l,xx,a,xx-1,num*2),fnd(xx,r,xx,b,num*2+1))+mod[num];
}Если же имелось ввиду установить равными иксу, то нужно хранить, одинаковые ли значения на данном отрезке и если одинаковые то чему они равны. При запросе просто проталкивать эту информацию к потомкам.
3 2011-09-21 20:19:14 Отредактировано NotImplemented (2011-09-22 20:12:30)
Re: дерево отрезков
Вопрос снова приобрел актуальность. Возможна ли модификация на прямоугольнике за O(logN*logN) и дополнительной памяти O(N*N)?