diff --git a/Android.bp b/Android.bp
index 6cb0053..db1ef89 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11304,6 +11304,7 @@
     name: "perfetto_src_trace_processor_containers_unittests",
     srcs: [
         "src/trace_processor/containers/bit_vector_unittest.cc",
+        "src/trace_processor/containers/implicit_segment_forest_unittest.cc",
         "src/trace_processor/containers/null_term_string_view_unittest.cc",
         "src/trace_processor/containers/row_map_unittest.cc",
         "src/trace_processor/containers/string_pool_unittest.cc",
diff --git a/BUILD b/BUILD
index 12fe725..0608cb1 100644
--- a/BUILD
+++ b/BUILD
@@ -1366,6 +1366,7 @@
         ":include_perfetto_public_base",
         ":include_perfetto_public_protozero",
         "src/trace_processor/containers/bit_vector.h",
+        "src/trace_processor/containers/implicit_segment_forest.h",
         "src/trace_processor/containers/null_term_string_view.h",
         "src/trace_processor/containers/row_map.h",
         "src/trace_processor/containers/row_map_algorithms.h",
diff --git a/src/trace_processor/containers/BUILD.gn b/src/trace_processor/containers/BUILD.gn
index 43e9603..c724df8 100644
--- a/src/trace_processor/containers/BUILD.gn
+++ b/src/trace_processor/containers/BUILD.gn
@@ -22,6 +22,7 @@
 perfetto_component("containers") {
   public = [
     "bit_vector.h",
+    "implicit_segment_forest.h",
     "null_term_string_view.h",
     "row_map.h",
     "row_map_algorithms.h",
@@ -44,6 +45,7 @@
   testonly = true
   sources = [
     "bit_vector_unittest.cc",
+    "implicit_segment_forest_unittest.cc",
     "null_term_string_view_unittest.cc",
     "row_map_unittest.cc",
     "string_pool_unittest.cc",
diff --git a/src/trace_processor/containers/implicit_segment_forest.h b/src/trace_processor/containers/implicit_segment_forest.h
new file mode 100644
index 0000000..f699181
--- /dev/null
+++ b/src/trace_processor/containers/implicit_segment_forest.h
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2024 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 SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "perfetto/base/logging.h"
+
+namespace perfetto::trace_processor {
+
+// An implementation of a segment tree data structure [1] with:
+// 1) parent-child relationships are implicit, saving memory.
+// 2) the requirement for the number of values being a power of two, turning
+//    the tree into a forest.
+//
+// Segment trees are a very powerful data structure allowing O(log(n)) aggregate
+// queries to be performed on an arbitrary range of elements in an array.
+// Specifically, for `T x[n]`, and an associative and commutative operation
+// AggOp (e.g. +, *, min, max, etc.), segment trees can compute
+// ```
+//   T y = AggOp()(x[i], x[i + 1], x[i + 2], ..., x[j])
+// ```
+// in O(log(n)) time.
+//
+// Practically, in trace processor, this is useful for computing aggregations
+// over events in a trace. For example:
+// ```
+// struct Slice { int64_t ts; int64_t dur; };
+// struct MaxDurSlice {
+//   Slice operator()(const Slice& a, const Slice& b) {
+//     return a.dur < b.dur ? b : a;
+//   }
+// }
+// using MipMap = ImplicitSegmentForest<Slice, MaxDurSlice>;
+// ```
+// allows building a "mipmap" [2] of a track in a trace in a UI. The UI can show
+// a representation of the items in the track when very zoomed out while
+// skipping the rendering slices which are smaller than one pixel.
+//
+// The design and implementation of this class takes heavy inspiration from
+// Tristan Hume's "IForestIndex" data structure [3] as described in his blog
+// post [4].
+//
+// [1] https://en.algorithmica.org/hpc/data-structures/segment-trees/
+// [2] https://en.wikipedia.org/wiki/Mipmap
+// [3]
+// https://github.com/trishume/gigatrace/blob/dfde0d7244f356bdc9aeefb387d904dd8b09d94a/src/iforest.rs
+// [4] https://thume.ca/2021/03/14/iforests/
+template <typename T, typename AggOp>
+class ImplicitSegmentForest {
+ public:
+  // Computes the aggregation (as specified by operator() in AggOp) over all
+  // elements in the tree between the indices [start, end). Requires that
+  // start < end.
+  //
+  // Complexity:
+  // This function performs O(log(n)) operations (n = end - start).
+  //
+  // Returns:
+  //  1) values[start]: if start + 1 == end
+  //  2) AggOp()(values[start], ..., values[end - 1]) otherwise
+  T Query(uint32_t start, uint32_t end) const {
+    PERFETTO_DCHECK(start < end);
+
+    const uint32_t in_start = start * 2;
+    const uint32_t in_end = end * 2;
+
+    uint32_t first_skip = LargestPrefixInsideSkip(in_start, in_end);
+    T aggregated = values_[AggNode(in_start, first_skip)];
+    for (uint32_t i = in_start + first_skip; i < in_end;) {
+      uint32_t skip = LargestPrefixInsideSkip(i, in_end);
+      aggregated = AggOp()(aggregated, values_[AggNode(i, skip)]);
+      i += skip;
+    }
+    return aggregated;
+  }
+
+  // Pushes a new element to right-most part of the tree. This index of this
+  // element can be used in future calls to |Query|.
+  void Push(T v) {
+    values_.emplace_back(std::move(v));
+
+    size_t len = values_.size();
+    auto levels_to_index = static_cast<uint32_t>(__builtin_ctzl(~len)) - 1;
+
+    size_t cur = len - 1;
+    for (uint32_t level = 0; level < levels_to_index; ++level) {
+      size_t prev_higher_level = cur - (1 << level);
+      values_[prev_higher_level] =
+          AggOp()(values_[prev_higher_level], values_[cur]);
+      cur = prev_higher_level;
+    }
+    values_.emplace_back(values_[len - (1 << levels_to_index)]);
+  }
+
+  // Returns the value at |n| in the tree: this corresponds to the |n|th
+  // element |Push|-ed into the tree.
+  const T& operator[](uint32_t n) { return values_[n * 2]; }
+
+ private:
+  static uint32_t Lsp(uint32_t x) { return x & -x; }
+  static uint32_t Msp(uint32_t x) {
+    return (1u << (sizeof(x) * 8 - 1)) >> __builtin_clz(x);
+  }
+  static uint32_t LargestPrefixInsideSkip(uint32_t min, uint32_t max) {
+    return Lsp(min | Msp(max - min));
+  }
+  static uint32_t AggNode(uint32_t i, uint32_t offset) {
+    return i + (offset >> 1) - 1;
+  }
+
+  std::vector<T> values_;
+};
+
+}  // namespace perfetto::trace_processor
+
+#endif  // SRC_TRACE_PROCESSOR_CONTAINERS_IMPLICIT_SEGMENT_FOREST_H_
diff --git a/src/trace_processor/containers/implicit_segment_forest_unittest.cc b/src/trace_processor/containers/implicit_segment_forest_unittest.cc
new file mode 100644
index 0000000..16dd262
--- /dev/null
+++ b/src/trace_processor/containers/implicit_segment_forest_unittest.cc
@@ -0,0 +1,76 @@
+/*
+ * Copyright (C) 2024 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 "src/trace_processor/containers/implicit_segment_forest.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto::trace_processor {
+namespace {
+
+struct Value {
+  uint32_t value;
+};
+
+struct Sum {
+  Value operator()(const Value& a, const Value& b) {
+    return Value{a.value + b.value};
+  }
+};
+
+TEST(ImplicitSegmentTree, SimpleSum) {
+  std::vector<uint32_t> res = {209, 330, 901, 3, 10, 0, 3903, 309, 490};
+
+  ImplicitSegmentForest<Value, Sum> forest;
+  for (uint32_t x : res) {
+    forest.Push(Value{x});
+  }
+
+  for (uint32_t i = 0; i < res.size(); ++i) {
+    for (uint32_t j = i + 1; j < res.size(); ++j) {
+      ASSERT_EQ(forest.Query(i, j).value,
+                std::accumulate(res.begin() + i, res.begin() + j, 0u));
+    }
+  }
+}
+
+TEST(ImplicitSegmentTree, Stress) {
+  static constexpr size_t kCount = 9249;
+  std::minstd_rand0 rng(42);
+
+  std::vector<uint32_t> res;
+  ImplicitSegmentForest<Value, Sum> forest;
+  for (uint32_t i = 0; i < kCount; ++i) {
+    res.push_back(static_cast<uint32_t>(rng()));
+    forest.Push(Value{res.back()});
+  }
+
+  for (uint32_t i = 0; i < 10000; ++i) {
+    uint32_t s = rng() % kCount;
+    uint32_t e = s + 1 + (rng() % (kCount - s));
+    ASSERT_EQ(forest.Query(s, e).value,
+              std::accumulate(res.begin() + s, res.begin() + e, 0u));
+  }
+}
+
+}  // namespace
+}  // namespace perfetto::trace_processor