A segment tree answers range queries (sum, min, max, …) over an array and updates single elements, both in O(log n). It is the structure to use when both operations are frequent, because a plain array makes queries slow and a prefix-sum array makes updates slow.

Segment tree of sums over [10, 20, 30, 40], stored in an array like a heap

arr = [10, 20, 30, 40]            index:  0   1   2   3

                [0..3] = 100                 tree[0]
               /            \
      [0..1] = 30          [2..3] = 70        tree[1]  tree[2]
      /       \            /       \
[0]=10     [1]=20    [2]=30     [3]=40        tree[3] tree[4] tree[5] tree[6]

tree array:  100  30  70  10  20  30  40
              0    1   2   3   4   5   6        children of i are 2i+1 and 2i+2

Why not a plain array or prefix sums?

Suppose x operations arrive, of which a quarter are range-sum queries and three quarters are updates. With a plain array queries cost O(n) and updates O(1), so the average is (x/4 · O(n) + 3x/4 · O(1)) / x = O(n). With a prefix-sum array it is the reverse — queries O(1), updates O(n) — and the average is again O(n). A segment tree makes both O(log n).

Structure	Range sum	Point update	Preprocessing	Space
Plain array	O(n)	O(1)	—	O(n)
Prefix-sum array	O(1)	O(n)	O(n)	O(n)
Segment tree	O(log n)	O(log n)	O(n)	O(n) (≈ 4n slots)
Binary indexed tree	O(log n)	O(log n)	O(n log n) (O(n) possible)	O(n) (n + 1 slots)

Size of the tree array

Children of node i live at 2i + 1 and 2i + 2, so the tree is stored in a plain array with no pointers. How large must it be?

If n is a power of two the tree is perfect: 2n − 1 nodes.
Otherwise let x be the smallest power of two greater than n; the tree needs at most 2x − 1 slots (some stay unused).
In practice allocate 4n — it is always enough (2x − 1 < 4n) and saves computing x.

size = 2 · 2^⌈log₂ n⌉ − 1 (≤ 4n)

Constructing the segment tree

build(ss, se, si)
ss/se = segment start/end in arr, si = index of this node in tree.
Leaf
ss == se → tree[si] = arr[ss].
Internal node
mid = (ss + se) / 2; tree[si] = build(ss, mid, 2si+1) + build(mid+1, se, 2si+2).

Python

def build(arr, tree, ss, se, si):
    if ss == se:                                        # leaf: a single element
        tree[si] = arr[ss]
        return tree[si]
    mid = (ss + se) // 2
    tree[si] = build(arr, tree, ss, mid, 2 * si + 1) + build(arr, tree, mid + 1, se, 2 * si + 2)
    return tree[si]                                     # parent = left sum + right sum

def tree_size(n):
    x = 1
    while x < n:                                        # smallest power of two ≥ n
        x *= 2
    return 2 * x - 1

arr = [10, 20, 30, 40]
tree = [0] * tree_size(len(arr))
build(arr, tree, 0, len(arr) - 1, 0)
print("tree:", " ".join(map(str, tree)))

C++

#include <iostream>
#include <vector>
using namespace std;

int build(const vector<int>& arr, vector<int>& tree, int ss, int se, int si) {
    if (ss == se) return tree[si] = arr[ss];            // leaf: a single element
    int mid = (ss + se) / 2;
    return tree[si] = build(arr, tree, ss, mid, 2 * si + 1)
                    + build(arr, tree, mid + 1, se, 2 * si + 2);   // parent = left sum + right sum
}

int treeSize(int n) {
    int x = 1;
    while (x < n) x *= 2;                                // smallest power of two ≥ n
    return 2 * x - 1;
}

int main() {
    vector<int> arr = {10, 20, 30, 40};
    int n = arr.size();
    vector<int> tree(treeSize(n), 0);
    build(arr, tree, 0, n - 1, 0);
    cout << "tree:";
    for (int v : tree) cout << " " << v;
    cout << "\n";
}

Java

public class Main {
    static int build(int[] arr, int[] tree, int ss, int se, int si) {
        if (ss == se) return tree[si] = arr[ss];        // leaf: a single element
        int mid = (ss + se) / 2;
        return tree[si] = build(arr, tree, ss, mid, 2 * si + 1)
                        + build(arr, tree, mid + 1, se, 2 * si + 2);   // parent = left sum + right sum
    }

    static int treeSize(int n) {
        int x = 1;
        while (x < n) x *= 2;                            // smallest power of two ≥ n
        return 2 * x - 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        int[] tree = new int[treeSize(arr.length)];
        build(arr, tree, 0, arr.length - 1, 0);
        StringBuilder sb = new StringBuilder("tree:");
        for (int v : tree) sb.append(' ').append(v);
        System.out.println(sb);
    }
}

JavaScript

function build(arr, tree, ss, se, si) {
    if (ss === se) return (tree[si] = arr[ss]);         // leaf: a single element
    const mid = Math.floor((ss + se) / 2);
    return (tree[si] = build(arr, tree, ss, mid, 2 * si + 1)
                     + build(arr, tree, mid + 1, se, 2 * si + 2));   // parent = left sum + right sum
}

function treeSize(n) {
    let x = 1;
    while (x < n) x *= 2;                                // smallest power of two ≥ n
    return 2 * x - 1;
}

const arr = [10, 20, 30, 40];
const tree = new Array(treeSize(arr.length)).fill(0);
build(arr, tree, 0, arr.length - 1, 0);
console.log("tree:", tree.join(" "));

Output

tree: 100 30 70 10 20 30 40

Time O(n) — each of the ≈ 2n nodes is computed once · Space O(n)

Range query

The three cases — at most two nodes per level are partially overlapped, so the query touches O(log n) nodes

getSum(1, 2) on [10, 20, 30, 40]

         [0..3]  partial overlap → recurse
        /      \
  [0..1] partial  [2..3] partial
  /    \          /    \
[0]    [1]      [2]    [3]
outside inside  inside outside
  0     20       30      0        → 20 + 30 = 50

Python

def build(arr, tree, ss, se, si):
    if ss == se:
        tree[si] = arr[ss]
        return tree[si]
    mid = (ss + se) // 2
    tree[si] = build(arr, tree, ss, mid, 2 * si + 1) + build(arr, tree, mid + 1, se, 2 * si + 2)
    return tree[si]

def get_sum_rec(tree, qs, qe, ss, se, si):
    if qe < ss or qs > se:                              # segment completely outside the query
        return 0
    if qs <= ss and se <= qe:                           # segment completely inside the query
        return tree[si]
    mid = (ss + se) // 2                                # partial overlap: ask both children
    return get_sum_rec(tree, qs, qe, ss, mid, 2 * si + 1) + get_sum_rec(tree, qs, qe, mid + 1, se, 2 * si + 2)

def get_sum(tree, n, qs, qe):
    if qs < 0 or qe > n - 1 or qs > qe:
        raise ValueError("invalid range")
    return get_sum_rec(tree, qs, qe, 0, n - 1, 0)

arr = [10, 20, 30, 40]
n = len(arr)
x = 1
while x < n:
    x *= 2
tree = [0] * (2 * x - 1)
build(arr, tree, 0, n - 1, 0)
print("tree:", " ".join(map(str, tree)))
for qs, qe in [(0, 2), (1, 3), (2, 2)]:
    print(f"sum({qs}, {qe}):", get_sum(tree, n, qs, qe))

C++

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

int build(const vector<int>& arr, vector<int>& tree, int ss, int se, int si) {
    if (ss == se) return tree[si] = arr[ss];
    int mid = (ss + se) / 2;
    return tree[si] = build(arr, tree, ss, mid, 2 * si + 1) + build(arr, tree, mid + 1, se, 2 * si + 2);
}

int getSumRec(const vector<int>& tree, int qs, int qe, int ss, int se, int si) {
    if (qe < ss || qs > se) return 0;                   // segment completely outside the query
    if (qs <= ss && se <= qe) return tree[si];          // segment completely inside the query
    int mid = (ss + se) / 2;                             // partial overlap: ask both children
    return getSumRec(tree, qs, qe, ss, mid, 2 * si + 1) + getSumRec(tree, qs, qe, mid + 1, se, 2 * si + 2);
}

int getSum(const vector<int>& tree, int n, int qs, int qe) {
    if (qs < 0 || qe > n - 1 || qs > qe) throw invalid_argument("invalid range");
    return getSumRec(tree, qs, qe, 0, n - 1, 0);
}

int main() {
    vector<int> arr = {10, 20, 30, 40};
    int n = arr.size(), x = 1;
    while (x < n) x *= 2;
    vector<int> tree(2 * x - 1, 0);
    build(arr, tree, 0, n - 1, 0);
    cout << "tree:";
    for (int v : tree) cout << " " << v;
    cout << "\n";
    int queries[3][2] = {{0, 2}, {1, 3}, {2, 2}};
    for (auto& q : queries) cout << "sum(" << q[0] << ", " << q[1] << "): " << getSum(tree, n, q[0], q[1]) << "\n";
}

Java

public class Main {
    static int build(int[] arr, int[] tree, int ss, int se, int si) {
        if (ss == se) return tree[si] = arr[ss];
        int mid = (ss + se) / 2;
        return tree[si] = build(arr, tree, ss, mid, 2 * si + 1) + build(arr, tree, mid + 1, se, 2 * si + 2);
    }

    static int getSumRec(int[] tree, int qs, int qe, int ss, int se, int si) {
        if (qe < ss || qs > se) return 0;               // segment completely outside the query
        if (qs <= ss && se <= qe) return tree[si];      // segment completely inside the query
        int mid = (ss + se) / 2;                         // partial overlap: ask both children
        return getSumRec(tree, qs, qe, ss, mid, 2 * si + 1) + getSumRec(tree, qs, qe, mid + 1, se, 2 * si + 2);
    }

    static int getSum(int[] tree, int n, int qs, int qe) {
        if (qs < 0 || qe > n - 1 || qs > qe) throw new IllegalArgumentException("invalid range");
        return getSumRec(tree, qs, qe, 0, n - 1, 0);
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        int n = arr.length, x = 1;
        while (x < n) x *= 2;
        int[] tree = new int[2 * x - 1];
        build(arr, tree, 0, n - 1, 0);
        StringBuilder sb = new StringBuilder("tree:");
        for (int v : tree) sb.append(' ').append(v);
        System.out.println(sb);
        int[][] queries = {{0, 2}, {1, 3}, {2, 2}};
        for (int[] q : queries) System.out.println("sum(" + q[0] + ", " + q[1] + "): " + getSum(tree, n, q[0], q[1]));
    }
}

JavaScript

function build(arr, tree, ss, se, si) {
    if (ss === se) return (tree[si] = arr[ss]);
    const mid = Math.floor((ss + se) / 2);
    return (tree[si] = build(arr, tree, ss, mid, 2 * si + 1) + build(arr, tree, mid + 1, se, 2 * si + 2));
}

function getSumRec(tree, qs, qe, ss, se, si) {
    if (qe < ss || qs > se) return 0;                   // segment completely outside the query
    if (qs <= ss && se <= qe) return tree[si];          // segment completely inside the query
    const mid = Math.floor((ss + se) / 2);               // partial overlap: ask both children
    return getSumRec(tree, qs, qe, ss, mid, 2 * si + 1) + getSumRec(tree, qs, qe, mid + 1, se, 2 * si + 2);
}

function getSum(tree, n, qs, qe) {
    if (qs < 0 || qe > n - 1 || qs > qe) throw new Error("invalid range");
    return getSumRec(tree, qs, qe, 0, n - 1, 0);
}

const arr = [10, 20, 30, 40];
const n = arr.length;
let x = 1;
while (x < n) x *= 2;
const tree = new Array(2 * x - 1).fill(0);
build(arr, tree, 0, n - 1, 0);
console.log("tree:", tree.join(" "));
for (const [qs, qe] of [[0, 2], [1, 3], [2, 2]]) console.log(`sum(${qs}, ${qe}):`, getSum(tree, n, qs, qe));

Output

tree: 100 30 70 10 20 30 40
sum(0, 2): 60
sum(1, 3): 90
sum(2, 2): 30

Time O(log n) per query · Space O(log n) recursion depth

Point update

Compute the difference
diff = new_val − arr[i]; also store arr[i] = new_val so later updates compute the right difference.
update(ss, se, i, si, diff)
If i is outside [ss, se] → return (this subtree is untouched).
Add and descend
tree[si] += diff; if the segment has more than one element, recurse into both children (only the one containing i does any work).

Exactly one node per level changes

update(1, 60) on [10, 20, 30, 40]: diff = 60 − 20 = +40

         [0..3] 100 → 140            ← contains index 1: += 40
        /            \
  [0..1] 30 → 70      [2..3] 70       ← index 1 not in [2..3]: skip
  /       \
[0] 10    [1] 20 → 60                 ← the leaf itself

Python

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr[:]
        self.n = len(arr)
        x = 1
        while x < self.n:
            x *= 2
        self.tree = [0] * (2 * x - 1)
        self._build(0, self.n - 1, 0)

    def _build(self, ss, se, si):
        if ss == se:
            self.tree[si] = self.arr[ss]
            return self.tree[si]
        mid = (ss + se) // 2
        self.tree[si] = self._build(ss, mid, 2 * si + 1) + self._build(mid + 1, se, 2 * si + 2)
        return self.tree[si]

    def get_sum(self, qs, qe, ss=0, se=None, si=0):
        if se is None:
            se = self.n - 1
        if qe < ss or qs > se:
            return 0
        if qs <= ss and se <= qe:
            return self.tree[si]
        mid = (ss + se) // 2
        return self.get_sum(qs, qe, ss, mid, 2 * si + 1) + self.get_sum(qs, qe, mid + 1, se, 2 * si + 2)

    def update(self, i, new_val):
        diff = new_val - self.arr[i]                    # how much every ancestor must change
        self.arr[i] = new_val
        self._update(0, self.n - 1, i, 0, diff)

    def _update(self, ss, se, i, si, diff):
        if i < ss or i > se:                            # index not in this segment
            return
        self.tree[si] += diff                           # this node's segment contains i
        if ss < se:
            mid = (ss + se) // 2
            self._update(ss, mid, i, 2 * si + 1, diff)
            self._update(mid + 1, se, i, 2 * si + 2, diff)

st = SegmentTree([10, 20, 30, 40])
print("tree:", " ".join(map(str, st.tree)))
print("sum(0, 2):", st.get_sum(0, 2))
print("update(1, 60)")
st.update(1, 60)
print("tree:", " ".join(map(str, st.tree)))
print("sum(0, 2):", st.get_sum(0, 2))
print("sum(1, 3):", st.get_sum(1, 3))

C++

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    vector<int> arr, tree;
    int n;
    int build(int ss, int se, int si) {
        if (ss == se) return tree[si] = arr[ss];
        int mid = (ss + se) / 2;
        return tree[si] = build(ss, mid, 2 * si + 1) + build(mid + 1, se, 2 * si + 2);
    }
    int getSum(int qs, int qe, int ss, int se, int si) const {
        if (qe < ss || qs > se) return 0;
        if (qs <= ss && se <= qe) return tree[si];
        int mid = (ss + se) / 2;
        return getSum(qs, qe, ss, mid, 2 * si + 1) + getSum(qs, qe, mid + 1, se, 2 * si + 2);
    }
    void update(int ss, int se, int i, int si, int diff) {
        if (i < ss || i > se) return;                   // index not in this segment
        tree[si] += diff;                               // this node's segment contains i
        if (ss < se) {
            int mid = (ss + se) / 2;
            update(ss, mid, i, 2 * si + 1, diff);
            update(mid + 1, se, i, 2 * si + 2, diff);
        }
    }
public:
    SegmentTree(const vector<int>& a) : arr(a), n(a.size()) {
        int x = 1;
        while (x < n) x *= 2;
        tree.assign(2 * x - 1, 0);
        build(0, n - 1, 0);
    }
    int getSum(int qs, int qe) const { return getSum(qs, qe, 0, n - 1, 0); }
    void update(int i, int newVal) {
        int diff = newVal - arr[i];                     // how much every ancestor must change
        arr[i] = newVal;
        update(0, n - 1, i, 0, diff);
    }
    void print() const { cout << "tree:"; for (int v : tree) cout << " " << v; cout << "\n"; }
};

int main() {
    SegmentTree st({10, 20, 30, 40});
    st.print();
    cout << "sum(0, 2): " << st.getSum(0, 2) << "\n";
    cout << "update(1, 60)\n";
    st.update(1, 60);
    st.print();
    cout << "sum(0, 2): " << st.getSum(0, 2) << "\n";
    cout << "sum(1, 3): " << st.getSum(1, 3) << "\n";
}

Java

public class Main {
    static class SegmentTree {
        int[] arr, tree;
        int n;
        SegmentTree(int[] a) {
            arr = a.clone(); n = a.length;
            int x = 1;
            while (x < n) x *= 2;
            tree = new int[2 * x - 1];
            build(0, n - 1, 0);
        }
        int build(int ss, int se, int si) {
            if (ss == se) return tree[si] = arr[ss];
            int mid = (ss + se) / 2;
            return tree[si] = build(ss, mid, 2 * si + 1) + build(mid + 1, se, 2 * si + 2);
        }
        int getSum(int qs, int qe) { return getSum(qs, qe, 0, n - 1, 0); }
        int getSum(int qs, int qe, int ss, int se, int si) {
            if (qe < ss || qs > se) return 0;
            if (qs <= ss && se <= qe) return tree[si];
            int mid = (ss + se) / 2;
            return getSum(qs, qe, ss, mid, 2 * si + 1) + getSum(qs, qe, mid + 1, se, 2 * si + 2);
        }
        void update(int i, int newVal) {
            int diff = newVal - arr[i];                 // how much every ancestor must change
            arr[i] = newVal;
            update(0, n - 1, i, 0, diff);
        }
        void update(int ss, int se, int i, int si, int diff) {
            if (i < ss || i > se) return;               // index not in this segment
            tree[si] += diff;                           // this node's segment contains i
            if (ss < se) {
                int mid = (ss + se) / 2;
                update(ss, mid, i, 2 * si + 1, diff);
                update(mid + 1, se, i, 2 * si + 2, diff);
            }
        }
        String dump() { StringBuilder sb = new StringBuilder("tree:"); for (int v : tree) sb.append(' ').append(v); return sb.toString(); }
    }

    public static void main(String[] args) {
        SegmentTree st = new SegmentTree(new int[]{10, 20, 30, 40});
        System.out.println(st.dump());
        System.out.println("sum(0, 2): " + st.getSum(0, 2));
        System.out.println("update(1, 60)");
        st.update(1, 60);
        System.out.println(st.dump());
        System.out.println("sum(0, 2): " + st.getSum(0, 2));
        System.out.println("sum(1, 3): " + st.getSum(1, 3));
    }
}

JavaScript

class SegmentTree {
    constructor(a) {
        this.arr = [...a]; this.n = a.length;
        let x = 1;
        while (x < this.n) x *= 2;
        this.tree = new Array(2 * x - 1).fill(0);
        this.build(0, this.n - 1, 0);
    }
    build(ss, se, si) {
        if (ss === se) return (this.tree[si] = this.arr[ss]);
        const mid = Math.floor((ss + se) / 2);
        return (this.tree[si] = this.build(ss, mid, 2 * si + 1) + this.build(mid + 1, se, 2 * si + 2));
    }
    getSum(qs, qe, ss = 0, se = this.n - 1, si = 0) {
        if (qe < ss || qs > se) return 0;
        if (qs <= ss && se <= qe) return this.tree[si];
        const mid = Math.floor((ss + se) / 2);
        return this.getSum(qs, qe, ss, mid, 2 * si + 1) + this.getSum(qs, qe, mid + 1, se, 2 * si + 2);
    }
    update(i, newVal) {
        const diff = newVal - this.arr[i];              // how much every ancestor must change
        this.arr[i] = newVal;
        this.updateRec(0, this.n - 1, i, 0, diff);
    }
    updateRec(ss, se, i, si, diff) {
        if (i < ss || i > se) return;                   // index not in this segment
        this.tree[si] += diff;                          // this node's segment contains i
        if (ss < se) {
            const mid = Math.floor((ss + se) / 2);
            this.updateRec(ss, mid, i, 2 * si + 1, diff);
            this.updateRec(mid + 1, se, i, 2 * si + 2, diff);
        }
    }
}

const st = new SegmentTree([10, 20, 30, 40]);
console.log("tree:", st.tree.join(" "));
console.log("sum(0, 2):", st.getSum(0, 2));
console.log("update(1, 60)");
st.update(1, 60);
console.log("tree:", st.tree.join(" "));
console.log("sum(0, 2):", st.getSum(0, 2));
console.log("sum(1, 3):", st.getSum(1, 3));

Output

tree: 100 30 70 10 20 30 40
sum(0, 2): 60
update(1, 60)
tree: 140 70 70 10 60 30 40
sum(0, 2): 100
sum(1, 3): 130

Time O(log n) per update · Space O(log n) recursion depth

Interview Q&A

Segment tree vs binary indexed tree — which one and why?

Why is a range query O(log n) when it may recurse into both children?

How much memory does a segment tree need and why 4n?

How would you support range updates (add v to every element in [l, r])?

Can a segment tree be built for an array that grows?