// img must be square with width/height being a power of 2
static Pair<BWImage> bwImageContrastQuadtree(BWImage img) {
  int w = img.getWidth(), h = img.getHeight();
  assertEquals("width/height", w, h);
  if (!isPowerOf2(w)) fail("image size not a power of 2: " + w);
  BWImage min = new(w, h);
  BWImage max = new(w, h);
  bwImageContrastQuadtree_make(img, min, max, 0, 0, w);
  ret pair(min, max);
}

svoid bwImageContrastQuadtree_make(BWImage img, BWImage min, BWImage max, int x, int y, int w) {
  int val = img.getInt(x, y);
  if (w == 1) {
    min.setInt(x, y, val);
    max.setInt(x, y, val);
  } else {
    int r = w/2;
    // process 4 subsquares
    bwImageContrastQuadtree_make(img, min, max, x+r, y+r, r);
    bwImageContrastQuadtree_make(img, min, max, x+r, y, r);
    bwImageContrastQuadtree_make(img, min, max, x, y+r, r);
    bwImageContrastQuadtree_make(img, min, max, x, y, r);
    
    // bottom right square is ok, process the 3 other ones
    int minTR, maxTR, minBL, maxBL,
      minBR = min.getInt(x+r, y+r),
      maxBR = max.getInt(x+r, y+r);
    min.setInt(x+r, y, minTR = min(min.getInt(x+r, y), minBR));
    max.setInt(x+r, y, maxTR = max(max.getInt(x+r, y), maxBR));
    
    min.setInt(x, y+r, minBL = min(min.getInt(x, y+r), minBR));
    max.setInt(x, y+r, maxBL = max(max.getInt(x, y+r), maxBR));
    
    min.setInt(x, y, min3(min.getInt(x, y), minTR, minBL));
    max.setInt(x, y, max3(max.getInt(x, y), maxTR, maxBL));
  }
}