Does anyone have implementation of BIT for following operations:

`setmin(i, x) = a[i] := min(a[i], x)`

`getmin(l, r) = min(a[x], l <= x <= r)`

Does anyone have implementation of BIT for following operations:

`add(l, r, x) = a[i] += x, where l <= i <= r`

`getsum(l, r) = sum(a[i]), where l <= i <= r`

These operations are not supported by BIT. Use segment tree instead.

Let's wait for more experienced coders.

There are the ways, that use more memory and time for doing that operations using BIT, but it's still faster than using segment tree.

For the second problem:

let y[i] = x[i]-x[i-1] let z[i] = y[i] * i

for example sum(1..3) x[i] = x[1] + x[2] + x[3] x[1] = x[1] x[2] = y[2] + y[1]; x[3] = y[3] + y[2] + y[1]

so x[1]+x[2]+x[3] = 4(y[1]+y[2]+y[3])-1*x[1]-2 * x[2]-3 * x[3] = 4 * (y[1] + y[2] + y[3])-(z[1] + z[2] + z[3])

we can infer that

sum(1..n) x[i] = sum(1..n) n * y[i]-sum(1..n) i * y[i] = sum(1..n) n * y[i]-sum(1..n) z[i]

notice that each modification can modify at most two elements of y[] and z[] so we can use two BITs to maintain y[] and z[]

For the first problem:

if l is always the first element of a[], then the normal BIT can support these operations easily. but I can't come up with ideas when l can be other element.

It won't do. Once you try to increase element, there is no reliable way to determine the new value for all intervals, which contain it. You can only decrease elements in this case.

Upd. Sorry, didn't notice min(a[i],x) in topic

for the first one there is easy to remember short code

Yes, thanks. I've seen you wrote that in another blog.

But I still want to learn, how to do it easily using BIT.

Could you please explain how this works ? And why do N have to be power of 2 ?

Actually it is segment tree...

plz explain me

how can you sure that po+N be the leaf node if N=1<<17

what happened if i use N=1<<25

it is possible that leaf node can be left or right of pos+N

then what to do?

plz explain me how can you sure that po+N be the leaf node if N=1<<17 what happened if i use N=1<<25 it is possible that leaf node can be left or right of pos+N then what to do?

Can you explain what is BIT? Is it binary search tree or Fenwick tree?

It's Fenwick Tree.

Binary indexed tree.

For the second problem I found this very short implementation some time ago, but I didn't analyze it.

For the first problem:

Obviously, setmin(i, x) can be rewritten as setvalue(i, x) if x < a[i], or otherwise ignore the operation. setvalue(i, x) = a[i] := x.

Next, I keep 2 arrays T and a. a is the current array, while T is my Fenwick tree. But instead of keeping minimal value of a range in the Fenwick, I keep index of that value in the a array.

define bit(i) (i & -i)

int que( int l, int r ) { //returns the index of the minimal value in a

}

void upd( int x, int val ) {

}

Both operations run in O(log^2) time worst case. However, execution time for big inputs is comparable with times of segment trees.