Adding code for 2D segment tree.

2 files changed, 61 insertions, 2 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 792fc93..87d2a6d 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -5,8 +5,9 @@
 
 \subsection{Segmentbaum}
 \lstinputlisting{datastructures/segmentTree.cpp}
-Mit \lstinline{update()} können ganze Intervalle geändert werden.
-Dazu: Offset in den inneren Knoten des Baums speichern.
+
+\subsection{2D-Segmentbaum}
+\lstinputlisting{datastructures/segmentTree2D.cpp}
 
 \subsection{Fenwick Tree}
 \lstinputlisting{datastructures/fenwickTree.cpp}
diff --git a/datastructures/segmentTree2D.cpp b/datastructures/segmentTree2D.cpp
new file mode 100644
index 0000000..a9d129b
--- /dev/null
+++ b/datastructures/segmentTree2D.cpp
@@ -0,0 +1,58 @@
+// 1-indiziert. Array t: [4*n][4*m]. Nur die _x-Varianten aufrufen.
+// Laufzeit: build: O(n*m), update, sum: O(log(n)*log(m))
+void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
+  if (ly == ry) {
+    if (lx == rx)vt[vx][vy] = a[lx][ly];
+    else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
+  } else {
+    int my = (ly + ry) / 2;
+    build_y(vx, lx, rx, vy*2, ly, my);
+    build_y(vx, lx, rx, vy*2+1, my+1, ry);
+    t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
+}}
+ 
+void build_x(int vx = 1, int lx = 0, int rx = N-1) {
+  if (lx != rx) {
+    int mx = (lx + rx) / 2;
+    build_x(vx*2, lx, mx);
+    build_x(vx*2+1, mx+1, rx);
+  }
+  build_y(vx, lx, rx, 1, 0, m-1);
+}
+
+int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
+  if (ly > ry) return 0;
+  if (ly == tly && try_ == ry) return t[vx][vy];
+  int tmy = (tly + try_) / 2;
+  return sum_y(vx, vy*2, tly, tmy, ly, min(ry,tmy))
+    + sum_y(vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
+}
+
+int sum_x(int vx=1, int tlx=0, int trx=n-1,int lx,int rx,int ly,int ry) {
+  if (lx > rx) return 0;
+  if (lx == tlx && trx == rx) return sum_y(vx, 1, 0, m-1, ly, ry);
+  int tmx = (tlx + trx) / 2;
+  return sum_x(vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
+    + sum_x(vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
+}
+
+void update_y(int vx, int lx, int rx, int vy, int ly, int ry,
+    int x, int y, int new_val) {
+  if (ly == ry) {
+    if (lx == rx) t[vx][vy] = new_val;
+    else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
+  } else {
+    int my = (ly + ry) / 2;
+    if (y <= my) update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
+    else update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
+    t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
+}}
+ 
+void update_x(int vx=1, int lx=0, int rx=n-1, int x, int y, int new_val) {
+  if (lx != rx) {
+    int mx = (lx + rx) / 2;
+    if (x <= mx) update_x(vx*2, lx, mx, x, y, new_val);
+    else update_x(vx*2+1, mx+1, rx, x, y, new_val);
+  }
+  update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
+}