How can I solve this problem UVA Problem 11297 — Census using **Binary Indexed Tree** ?

**Problem Description in Short :** Given a 2D grid (500x500 at most), I need to process 2 types of query.

- Change the value of grid[x][y] by Val
- Output the maximum and minimum number of a sub rectangle of
**grid**(x1,y1) to (x2,y2)

( **considering every input is valid** ) How can I solve this problem using **Binary Indexed Tree?** Also it will be a great hand if you help me to understand how **Range Minimum or Maximum Query** can be done by **BIT**.

Thanks in Advance :)

I don't think we can solve this problem with Binary Indexed Tree (Fenwick Tree). We can use Fenwick Tree only in cases:

maximize (or minimize)query instead ofchanging valuequery (i.e grid[x][y]=max(grid[x][y],val) ).However, we can solve this problem with

SegmentTree2D.Thank you skyvn97 for your reply. However I found this problem under

BITcategory in this site (29 th problem), So I was wondering if it can be solved byBIT..Then I searched a little and found two blogs that has code that can do

RMQusingBIT( at least they say so). Although I could not understand them. Right now I am not home and with a little access to internet, but I willedit this commentand provide links of those blogs no sooner I get back home. :)EditBlog LinksWell... Actually it seems that you can use BIT for this problem. But you need a bit special BIT which allows you to calculate not invertible function. You can read more about it here (Russian). But you still can only maximize/minimize but not change...

Ok, skyvn97 I'm back in home again. I found these two blogs interesting,

Please help me to understand how they used

BITto calculateRMQwhy do you only have one sequence? https://ioinformatics.org/journal/v9_2015_39_44.pdf

I copied Alias code from here.

No. RMQ is commutative, thus N can be any number.

that n in maxn because it makes a ballaced tree

keyvankhademi Can you Please elaborate your answer.. And help me to understand the idea of the code above.

The things I do not understand,

`const int N = 1 << 17; // has to be power of 2`

Why we set like it, why not set`const int N = 1 << 18;`

or`const int N = 1 << 19;`

or`const int N = 100000;`

At

`void SetMin(int pos, int x)`

we are iterating like`for (int i = pos + N; i; i >>= 1)`

why we addNwithpos, what's wrong if we do not addNwithposand just iterate like`for (int i = pos; i; i >>= 1)`

Also please describe the logic in this code portion

Thanks in Advance :)

what balance you talking about? What will be much more complicated? For example, there is my submission 7938499 with such segment tree and N = 1000010 — not a power of 2.

Power of 2 has no advantages. Only memory waste.

You can count all vertices that aren't in the last layer of tree and call it

`R`

. After that to have access to position`i`

you need just to return`tree[i + R]`

.Thanks keyvankhademi.. Big Time :)

i know that it's an old post , but today i just read a paper about RMQ with BIT so i decided to share it to everyone who are interested about this topic

http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

https://stackoverflow.com/questions/31106459/how-to-adapt-fenwick-tree-to-answer-range-minimum-queries/34602284#

prefer this as well!!