StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSegment tree 2D, sum of rectangle
text
Body
copied!<p>I really want to learn and implement segment tree 2D, at last. It's haunting me. I know the 1D case of segment tree, but somehow I can't manage with 2D. The problem is that I have a matrix 1024x1024 (so I use an array [2048][2048] as a tree) and I want to implement two operations:</p> <ol> <li>void insert(int x, int y, int val); - which assigns value val to element [x][y] of matrix </li> <li>int query(int x1, int y1, int x2, int y2); - which returns sum of the elements in matrix in rectangle (x1,y1,x2,y2)</li> </ol> <p>So far I wrote this:</p> <pre><code>const int M=1024; int tree[2*M][2*M]; void insert(int x, int y, int val) { int vx=M+x, vy=M+y; tree[vx][vy]=val; while(vy!=1) { vy/=2; tree[vx][vy]=tree[vx][2*vy]+tree[vx][2*vy+1]; } while(vx!=1) { vy=M+y; vx/=2; while(vy!=1) { vy/=2; tree[vx][vy]=tree[2*vx][2*vy]+tree[2*vx+1][2*vy+1]; } } } int query(int x1, int y1, int x2, int y2) { int vx1=M+x1, vy1=M+y1, vx2=M+x2, vy2=M+y2; int res=tree[vx1][vy1]; if(vx1!=vx2 || vy1!=vy2) res+=tree[vx2][vy2]; while(vx1/2 != vx2/2) { vy1=M+y1; vy2=M+y2; while(vy1/2 != vy2/2) { if(vx1%2==0 && vy1%2==0) res+=tree[vx1+1][vy1+1]; if(vx2%2==1 && vy2%2==1) res+=tree[vx2-1][vy2-1]; vy1/=2; vy2/=2; } vx1/=2; vx2/=2; } return res; } </code></pre> <p>But it doesn't work correctly. Say, for:</p> <p>insert(5,5,1); query(0,5,1000,5);</p> <p>It returns 0, instead of 1. I think the problem is in query (I hope insert is OK), that I don't fully understand the idea of this operation. In 1D I had no problems, but this case is difficult to imagine, for me.</p> <p>Can you please help me implement this correctly? I would be very grateful for help.</p> <p><strong>EDIT:</strong> maybe it will be better to show how I can do it in 1D, this code works and I think the idea i simple:</p> <pre><code>const int M=1024; int tree[2*M]; void insert(int x, int val) { int v=M+x; tree[v]=val; while(v!=1) { v/=2; tree[v]=tree[2*v]+tree[2*v+1]; } } int query(int a, int b) { int va=M+a, vb=M+b; int res=tree[va]; if(va!=vb) res+=tree[vb]; while(va/2 != vb/2) { if(va%2==0) res+=tree[va+1]; if(vb%2==1) res+=tree[vb-1]; va/=2; vb/=2; } return res; } </code></pre> <p>but unfortunately I can't apply it in 2D..</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload