diff --git a/src/main/java/com/android/tools/r8/utils/SegmentTree.java b/src/main/java/com/android/tools/r8/utils/SegmentTree.java
new file mode 100644
index 0000000..1fc95b0
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/SegmentTree.java
@@ -0,0 +1,82 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.utils;
+
+import java.util.Map;
+import java.util.TreeMap;
+
+/**
+ * Implementation of a discrete segment tree where intervals are specified by their start end and
+ * point. Both points are considered part of the interval.
+ */
+public class SegmentTree<V> {
+
+  private final TreeMap<Integer, V> internalTree = new TreeMap<>();
+  private final boolean allowIntervalOverwrites;
+
+  private int size = 0;
+
+  public SegmentTree(boolean allowIntervalOverwrites) {
+    this.allowIntervalOverwrites = allowIntervalOverwrites;
+  }
+
+  public V find(int point) {
+    Map.Entry<Integer, V> entry = findEntry(point);
+    return entry != null ? entry.getValue() : null;
+  }
+
+  public Map.Entry<Integer, V> findEntry(Integer point) {
+    Map.Entry<Integer, V> kvEntry = internalTree.floorEntry(point);
+    return (kvEntry == null || kvEntry.getValue() == null) ? null : kvEntry;
+  }
+
+  public SegmentTree<V> add(int start, int end, V value) {
+    Map.Entry<Integer, V> existingEndRange = findEntry(end);
+    Box<Integer> removedIntervals = new Box<>(0);
+    boolean removedKeys =
+        internalTree
+            .navigableKeySet()
+            .removeIf(
+                key -> {
+                  if (start < key && key <= end) {
+                    assert allowIntervalOverwrites;
+                    if (internalTree.get(key) != null) {
+                      removedIntervals.set(removedIntervals.get() + 1);
+                    }
+                    return true;
+                  }
+                  return false;
+                });
+    if (existingEndRange != null) {
+      assert allowIntervalOverwrites;
+      if (removedKeys) {
+        // We have counted a removed interval where it was actually just shortened:
+        // I1      |----------------------------------|
+        // I2   |--------|
+        // R    |--------||---------------------------|
+        // I1.start has been removed and counted, but it is actually just moved, so we decrease the
+        // removed counter by 1.
+        removedIntervals.set(removedIntervals.get() - 1);
+      }
+    }
+    internalTree.put(start, value);
+    if (!internalTree.containsKey(end + 1)) {
+      internalTree.put(end + 1, existingEndRange == null ? null : existingEndRange.getValue());
+    }
+    // We only count unique intervals, thus the following is two and not three intervals when
+    // adding I2:
+    // I1      |-------------------------------|
+    // I2              |------------|
+    // R       |------||------------||---------|
+    // However, if the order was reversed, we should remove one from the size count since I1
+    // completely shadows I2.
+    size = (size - removedIntervals.get()) + 1;
+    return this;
+  }
+
+  public int size() {
+    return size;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/SegmentTreeTests.java b/src/test/java/com/android/tools/r8/utils/SegmentTreeTests.java
new file mode 100644
index 0000000..bb2ea17
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/utils/SegmentTreeTests.java
@@ -0,0 +1,106 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.utils;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.util.Map;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class SegmentTreeTests extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public SegmentTreeTests(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  private SegmentTree<Integer> tree(boolean allowOverrides) {
+    return new SegmentTree<>(allowOverrides);
+  }
+
+  @Test
+  public void testInsertSimpleRange() {
+    SegmentTree<Integer> tree = tree(false).add(1, 100, 3);
+    Map.Entry<Integer, Integer> entry = tree.findEntry(50);
+    assertEntry(tree, 50, 1, 3);
+    assertNull(tree.find(0));
+    assertNull(tree.find(101));
+  }
+
+  @Test
+  public void testInsertMultipleRanges() {
+    SegmentTree<Integer> tree = tree(false).add(1, 10, 3).add(20, 30, 7).add(31, 100, 9);
+    assertEntry(tree, 10, 1, 3);
+    assertNull(tree.findEntry(11));
+    assertEntry(tree, 20, 20, 7);
+    assertEquals(tree.findEntry(31), tree.findEntry(100));
+    assertNull(tree.find(101));
+  }
+
+  @Test(expected = AssertionError.class)
+  public void testAssertingNoOverrides() {
+    tree(false).add(1, 10, 3).add(7, 2, 4);
+  }
+
+  @Test
+  public void testOverrideLeft() {
+    SegmentTree<Integer> tree = tree(true).add(7, 9, 2).add(6, 7, 1);
+    assertNull(tree.findEntry(5));
+    assertEntry(tree, 7, 6, 1);
+    assertEntry(tree, 9, 8, 2);
+    assertNull(tree.findEntry(10));
+    assertEquals(2, tree.size());
+  }
+
+  @Test
+  public void testOverrideRight() {
+    SegmentTree<Integer> tree = tree(true).add(6, 7, 1).add(7, 9, 2);
+    assertNull(tree.findEntry(5));
+    assertEntry(tree, 6, 6, 1);
+    assertEntry(tree, 8, 7, 2);
+    assertNull(tree.findEntry(10));
+    assertEquals(2, tree.size());
+  }
+
+  @Test
+  public void testOverrideContained() {
+    SegmentTree<Integer> tree = tree(true).add(0, 100, 1).add(25, 75, 2);
+    assertEntry(tree, 24, 0, 1);
+    assertEntry(tree, 75, 25, 2);
+    assertEntry(tree, 100, 76, 1);
+    assertNull(tree.findEntry(101));
+    assertEquals(2, tree.size());
+  }
+
+  @Test
+  public void testOverrideContainer() {
+    SegmentTree<Integer> tree = tree(true).add(25, 75, 2).add(0, 100, 1);
+    assertEntry(tree, 24, 0, 1);
+    assertEntry(tree, 75, 0, 1);
+    assertEntry(tree, 100, 0, 1);
+    assertNull(tree.findEntry(101));
+    assertEquals(1, tree.size());
+  }
+
+  private void assertEntry(
+      SegmentTree<Integer> tree, int index, int expectedStart, int expectedValue) {
+    assertEquals(expectedStart, (int) tree.findEntry(index).getKey());
+    assertEquals(expectedValue, (int) tree.findEntry(index).getValue());
+  }
+}