diff --git a/Android.bp b/Android.bp
index 51105eb..b3fbccf 100644
--- a/Android.bp
+++ b/Android.bp
@@ -804,6 +804,7 @@
         "payload_consumer/partition_writer_unittest.cc",
         "payload_consumer/extent_reader_unittest.cc",
         "payload_consumer/extent_writer_unittest.cc",
+        "payload_consumer/extent_map_unittest.cc",
         "payload_consumer/snapshot_extent_writer_unittest.cc",
         "payload_consumer/fake_file_descriptor.cc",
         "payload_consumer/file_descriptor_utils_unittest.cc",
diff --git a/common/utils.h b/common/utils.h
index 59f236e..4e78097 100644
--- a/common/utils.h
+++ b/common/utils.h
@@ -465,6 +465,17 @@
   DISALLOW_COPY_AND_ASSIGN(ScopedActionCompleter);
 };
 
+// Simple wrapper for creating a slice of some container,
+// similar to string_view but for other containers.
+template <typename T>
+struct Range {
+  Range(T t1, T t2) : t1_(t1), t2_(t2) {}
+  constexpr auto begin() const noexcept { return t1_; }
+  constexpr auto end() const noexcept { return t2_; }
+  T t1_;
+  T t2_;
+};
+
 }  // namespace chromeos_update_engine
 
 #define TEST_AND_RETURN_FALSE_ERRNO(_x)                              \
diff --git a/payload_consumer/extent_map.h b/payload_consumer/extent_map.h
new file mode 100644
index 0000000..aeb7066
--- /dev/null
+++ b/payload_consumer/extent_map.h
@@ -0,0 +1,90 @@
+//
+// Copyright (C) 2021 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#ifndef UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
+#define UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
+
+#include <functional>
+#include <map>
+#include <utility>
+
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+// Data structure for storing a disjoint set of extents.
+// Currently the only usecase is for VABCPartitionWriter to keep track of which
+// block belongs to which merge operation. Therefore this class only contains
+// the minimal set of functions needed.
+template <typename T, typename Comparator = ExtentLess>
+class ExtentMap {
+ public:
+  bool AddExtent(const Extent& extent, T&& value) {
+    if (Get(extent)) {
+      return false;
+    }
+    const auto& [it, inserted] = map_.insert({extent, std::forward<T>(value)});
+    if (inserted) {
+      set_.AddExtent(extent);
+    }
+    return inserted;
+  }
+
+  size_t size() const { return map_.size(); }
+
+  // Return a pointer to entry which is intersecting |extent|. If T is already
+  // a pointer type, return T on success. This function always return
+  // |nullptr| on failure. Therefore you cannot store nullptr as an entry.
+  std::optional<T> Get(const Extent& extent) const {
+    const auto it = map_.find(extent);
+    if (it == map_.end()) {
+      LOG_IF(WARNING, set_.OverlapsWithExtent(extent))
+          << "Looking up a partially intersecting extent isn't supported by "
+             "this data structure.";
+      return {};
+    }
+    return {it->second};
+  }
+
+  // Return a set of extents that are contained in this extent map.
+  // If |extent| is completely covered by this extent map, a vector of itself
+  // will be returned.
+  // If only a subset of |extent| is covered by this extent map, a vector of
+  // parts in this map will be returned.
+  // If |extent| has no intersection with this map, an empty vector will be
+  // returned.
+  // E.g. extent map contains [0,5] and [10,15], GetIntersectingExtents([3, 12])
+  // would return [3,5] and [10,12]
+  std::vector<Extent> GetIntersectingExtents(const Extent& extent) const {
+    return set_.GetIntersectingExtents(extent);
+  }
+
+  // Complement of |GetIntersectingExtents|, return vector of extents which are
+  // part of |extent| but not covered by this map.
+  std::vector<Extent> GetNonIntersectingExtents(const Extent& extent) const {
+    return FilterExtentRanges({extent}, set_);
+  }
+
+ private:
+  // Get a range of exents that potentially intersect with parameter |extent|
+  std::map<Extent, T, Comparator> map_;
+  ExtentRanges set_;
+};
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
diff --git a/payload_consumer/extent_map_unittest.cc b/payload_consumer/extent_map_unittest.cc
new file mode 100644
index 0000000..e7972cd
--- /dev/null
+++ b/payload_consumer/extent_map_unittest.cc
@@ -0,0 +1,122 @@
+//
+// Copyright (C) 2021 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include <gtest/gtest.h>
+#include <optional>
+
+#include "update_engine/payload_consumer/extent_map.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+
+namespace chromeos_update_engine {
+
+class ExtentMapTest : public ::testing::Test {
+ public:
+  ExtentMap<int> map_;
+};
+
+TEST_F(ExtentMapTest, QueryExactExtent) {
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
+  auto ret = map_.Get(ExtentForRange(0, 5));
+  ASSERT_NE(ret, std::nullopt);
+  ASSERT_EQ(*ret, 7);
+}
+
+TEST_F(ExtentMapTest, QuerySubset) {
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
+  auto ret = map_.Get(ExtentForRange(1, 2));
+  ASSERT_EQ(ret, std::nullopt);
+}
+
+TEST_F(ExtentMapTest, QueryTouching) {
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
+  auto ret = map_.Get(ExtentForRange(3, 2));
+  ASSERT_EQ(ret, std::nullopt);
+  ret = map_.Get(ExtentForRange(4, 1));
+  ASSERT_EQ(ret, std::nullopt);
+  ret = map_.Get(ExtentForRange(5, 5));
+  ASSERT_EQ(ret, std::nullopt);
+  ret = map_.Get(ExtentForRange(5, 6));
+  ASSERT_EQ(ret, std::nullopt);
+}
+
+TEST_F(ExtentMapTest, GetIntersectingExtents) {
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 7));
+  auto ret = std::vector<Extent>{};
+  ret = map_.GetIntersectingExtents(ExtentForRange(2, 10));
+  ASSERT_EQ(ret.size(), 2U);
+  ASSERT_EQ(ret[0].start_block(), 2U);
+  ASSERT_EQ(ret[0].num_blocks(), 3U);
+
+  ASSERT_EQ(ret[1].start_block(), 10U);
+  ASSERT_EQ(ret[1].num_blocks(), 2U);
+
+  ret = map_.GetIntersectingExtents(ExtentForRange(2, 17));
+  ASSERT_EQ(ret.size(), 2U);
+  ASSERT_EQ(ret[0].start_block(), 2U);
+  ASSERT_EQ(ret[0].num_blocks(), 3U);
+
+  ASSERT_EQ(ret[1].start_block(), 10U);
+  ASSERT_EQ(ret[1].num_blocks(), 5U);
+
+  ret = map_.GetIntersectingExtents(ExtentForRange(2, 2));
+  ASSERT_EQ(ret, std::vector<Extent>{ExtentForRange(2, 2)});
+
+  ret = map_.GetIntersectingExtents(ExtentForRange(10, 5));
+  ASSERT_EQ(ret, std::vector<Extent>{ExtentForRange(10, 5)});
+
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(20, 5), 7));
+  ret = map_.GetIntersectingExtents(ExtentForRange(0, 30));
+  ASSERT_EQ(ret.size(), 3U);
+  ASSERT_EQ(ret[0].start_block(), 0U);
+  ASSERT_EQ(ret[0].num_blocks(), 5U);
+
+  ASSERT_EQ(ret[1].start_block(), 10U);
+  ASSERT_EQ(ret[1].num_blocks(), 5U);
+
+  ASSERT_EQ(ret[2].start_block(), 20U);
+  ASSERT_EQ(ret[2].num_blocks(), 5U);
+}
+
+TEST_F(ExtentMapTest, GetNonIntersectingExtents) {
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 7));
+  ASSERT_TRUE(map_.AddExtent(ExtentForRange(20, 5), 7));
+
+  auto ret = std::vector<Extent>{};
+  ret = map_.GetNonIntersectingExtents(ExtentForRange(2, 13));
+
+  ASSERT_EQ(ret.size(), 1U);
+  ASSERT_EQ(ret[0].start_block(), 5U);
+  ASSERT_EQ(ret[0].num_blocks(), 5U);
+
+  ret = map_.GetNonIntersectingExtents(ExtentForRange(7, 20));
+  ASSERT_EQ(ret.size(), 3U);
+  ASSERT_EQ(ret[0].start_block(), 7U);
+  ASSERT_EQ(ret[0].num_blocks(), 3U);
+
+  ASSERT_EQ(ret[1].start_block(), 15U);
+  ASSERT_EQ(ret[1].num_blocks(), 5U);
+
+  ASSERT_EQ(ret[2].start_block(), 25U);
+  ASSERT_EQ(ret[2].num_blocks(), 2U);
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index 2098639..4cc2d6f 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -45,7 +45,7 @@
 
 bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
   if (a.start_block() == b.start_block())
-    return true;
+    return a.num_blocks() != 0;
   if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
     return false;
   if (a.start_block() < b.start_block()) {
@@ -281,6 +281,31 @@
   return out;
 }
 
+Range<ExtentRanges::ExtentSet::const_iterator> ExtentRanges::GetCandidateRange(
+    const Extent& extent) const {
+  auto lower_it = extent_set_.lower_bound(extent);
+  if (lower_it != extent_set_.begin()) {
+    --lower_it;
+  }
+
+  const auto upper_it = extent_set_.upper_bound(
+      ExtentForRange(extent.start_block() + extent.num_blocks(), 1));
+  return {lower_it, upper_it};
+}
+
+std::vector<Extent> ExtentRanges::GetIntersectingExtents(
+    const Extent& extent) const {
+  const auto candidates = GetCandidateRange(extent);
+  std::vector<Extent> result;
+  for (const auto& ext : candidates) {
+    if (auto intersection = GetOverlapExtent(ext, extent);
+        intersection.num_blocks() != 0) {
+      result.emplace_back(std::move(intersection));
+    }
+  }
+  return result;
+}
+
 vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
                                   const ExtentRanges& ranges) {
   vector<Extent> result;
@@ -331,4 +356,15 @@
   return result;
 }
 
+Extent GetOverlapExtent(const Extent& extent1, const Extent& extent2) {
+  if (!ExtentRanges::ExtentsOverlap(extent1, extent2)) {
+    return {};
+  }
+  const auto start_block =
+      std::max(extent1.start_block(), extent2.start_block());
+  const auto end_block = std::min(extent1.start_block() + extent1.num_blocks(),
+                                  extent2.start_block() + extent2.num_blocks());
+  return ExtentForRange(start_block, end_block - start_block);
+}
+
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
index 68aa27f..4894831 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -23,6 +23,7 @@
 
 #include <base/macros.h>
 
+#include "update_engine/common/utils.h"
 #include "update_engine/update_metadata.pb.h"
 
 // An ExtentRanges object represents an unordered collection of extents (and
@@ -84,6 +85,18 @@
   // the number of blocks in this extent set.
   std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const;
 
+  // Compute the intersection between this ExtentRange and the |extent|
+  // parameter. Return results in a vector. If there's no intersection, an empty
+  // vector is returned.
+  std::vector<Extent> GetIntersectingExtents(const Extent& extent) const;
+
+  // Get a range of extents that possibly intersect with |extent|. (Returned
+  // extents do not necessarily intersect!). It is perfectly acceptable to just
+  // return all extents in this set, though more efficient solution using binary
+  // search is preferred.
+  Range<ExtentSet::const_iterator> GetCandidateRange(
+      const Extent& extent) const;
+
  private:
   ExtentSet extent_set_;
   uint64_t blocks_;
@@ -95,6 +108,8 @@
 std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
                                        const ExtentRanges& ranges);
 
+Extent GetOverlapExtent(const Extent& extent1, const Extent& extent2);
+
 }  // namespace chromeos_update_engine
 
 #endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index f55bb73..314ec54 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -315,4 +315,20 @@
                 ranges));
 }
 
+TEST(ExtentRangesTest, GetOverlapExtent) {
+  const auto ret1 =
+      GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(10, 10));
+  ASSERT_EQ(ret1.num_blocks(), 0UL) << ret1;
+  const auto ret2 =
+      GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(9, 10));
+  ASSERT_EQ(ret2, ExtentForRange(9, 1));
+
+  const auto ret3 =
+      GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 10));
+  ASSERT_EQ(ret3, ExtentForRange(7, 5));
+  const auto ret4 =
+      GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 3));
+  ASSERT_EQ(ret4.num_blocks(), 0UL);
+}
+
 }  // namespace chromeos_update_engine