Problem:

Give a series of IP segments, for example, [0.0.0.1-0.0.0.3], [123.234.232.21-123.245.21.1]...

Now there is a new IP, find which IP segment it's in ?

Solution:

First, we could map the ends of IP segments into some intervals, since the IP address could be represented by a unsigned int. This is called discretization.

Second, setup the segment tree. Every leaf node is [x, x+1], it means whether an IP segment includes the part. We could use a vector<int> to record the interval index for searching. So the core code is:

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

#include <limits.h>

#include <assert.h>

#include <stdio.h>

using namespace std;

class Interval {

 public:

  int l, r;

  Interval(int ll = 0, int rr = 0) : l(ll), r(rr) {}

};

class Node {

 public:

  int l, r;

  Node *lc, *rc;

  vector<int> IPs;

  Node(int ll = 0, int rr = 0) : l(ll), r(rr), lc(NULL), rc(NULL) {}

};

Node* build(int l, int r) {

  Node *root = new Node();

  root->l = l, root->r = r;

  if (l + 1 >= r)

    return root;

  int mid = (l + r) / 2;

  root->lc = build(l, mid);

  root->rc = build(mid, r);

  return root;

}

void insert(Node* root, int l, int r, int idx) {

  if (l <= root->l && r >= root->r) {

    root->IPs.push_back(idx);

    return;

  }

  int mid = (root->l + root->r) / 2;

  if (l < mid) // Take care here!

    insert(root->lc, l, mid, idx);

  if (r > mid) // Take care here!

    insert(root->rc, mid, r, idx);

}

void search(Node* root, int l, int r, vector<int>& res) {

  if (r <= root->r && l >= root->l) {

    for (int i = 0; i < root->IPs.size(); ++i)

      res.push_back(root->IPs[i]);

  }

  int mid = (root->l + root->r) / 2;

  if (r <= mid)

    search(root->lc, l, mid, res);

  if (l >= mid)

    search(root->rc, mid, r, res);

}

int main()

{

  Node* rt = build(1, 7);

  Interval inters[] = {Interval(1,3),Interval(2,4),Interval(1,5), Interval(5,7)};

  int size = sizeof(inters) / sizeof(inters[0]);

  for (int i = 0; i < size; ++i)

    insert(rt, inters[i].l, inters[i].r, i);

  vector<int> res;

  search(rt, 2, 3, res);

  return 0;

}