Skip to main content

Segment Tree: Computing HP on the Battlefield

Imagine a battlefield represented by an ordered line of units. Each position stores the current health points, or HP, of one unit. During a game, the system may repeatedly ask questions such as:

  • What is the total HP of all units between positions 2 and 6?
  • How much HP remains in a selected region of the battlefield?
  • A unit at one position takes damage. How should the stored totals change?
  • A unit is healed. Can the total HP of a range be obtained quickly afterward?

These questions have two important forms. The first is a range-sum query: add the HP values in a continuous interval. The second is a point update: replace or change the HP value at one position.

A segment tree is designed for this combination of operations. It stores sums for carefully selected intervals, allowing both a range sum and a point update to be completed in O(log n) time, where n is the number of units. The initial construction takes O(n) time, and the data structure requires O(n) space.

This article develops the idea from the battlefield model, explains the tree shape and its invariant, follows range queries and HP updates step by step, and highlights the implementation decisions that most often cause errors.

1. The battlefield model​

Let the units be stored in an array:

HP = [12, 7, 10, 5, 8, 6, 11, 4]

The index identifies a unit's position in the ordered battlefield, and the value at that index is the unit's current HP. Position 0 has 12 HP, position 1 has 7 HP, and position 3 has 5 HP.

A range sum over positions 2 through 5 is:

10 + 5 + 8 + 6 = 29

Using a simple loop, this answer is easy to calculate. However, if the game asks many queries, repeatedly scanning every position in a range can become expensive. A range containing many positions may require O(n) work for one query in the worst case.

A point update also appears simple. If the unit at position 3 changes from 5 HP to 9 HP, the array becomes:

[12, 7, 10, 9, 8, 6, 11, 4]

Changing the original array value is not the difficult part. The difficulty is keeping previously computed range totals consistent after the change. A total for the entire battlefield, for example, includes position 3, so it must also change. The same is true for every stored interval containing that position.

A segment tree solves both problems by storing the total HP of many intervals at the same time.

2. The shape of a segment tree​

A segment tree is a binary tree built over an array interval. The root represents the complete range of positions. Each internal node represents one interval and divides it into two smaller intervals:

  • the left child represents the left portion;
  • the right child represents the right portion.

For eight positions, numbered 0 through 7, the logical shape is:

[0, 7]
├── [0, 3]
│   ├── [0, 1]
│   │   ├── [0, 0]
│   │   └── [1, 1]
│   └── [2, 3]
│       ├── [2, 2]
│       └── [3, 3]
└── [4, 7]
    ├── [4, 5]
    │   ├── [4, 4]
    │   └── [5, 5]
    └── [6, 7]
        ├── [6, 6]
        └── [7, 7]

A leaf represents one array position. An internal node represents the sum of all leaves in its interval. For the sample HP array, the values are:

[0, 7] = 63
├── [0, 3] = 34
│   ├── [0, 1] = 19
│   │   ├── [0, 0] = 12
│   │   └── [1, 1] = 7
│   └── [2, 3] = 15
│       ├── [2, 2] = 10
│       └── [3, 3] = 5
└── [4, 7] = 29
    ├── [4, 5] = 14
    │   ├── [4, 4] = 8
    │   └── [5, 5] = 6
    └── [6, 7] = 15
        ├── [6, 6] = 11
        └── [7, 7] = 4

The root stores the total HP of the entire battlefield. A node such as [2, 3] stores the total HP of positions 2 and 3. A node such as [4, 7] stores the total HP of positions 4 through 7. This hierarchy lets a query reuse a stored total for a complete interval instead of adding every individual unit again.

The tree does not store every possible interval. It stores a structured collection of intervals created by repeatedly splitting a range into two parts. That carefully chosen structure is what makes traversal and updates efficient.

3. The central invariant​

The most important rule, or invariant, is:

The value stored at a node representing interval [left, right] equals the sum of the HP values at every position from left through right.

For an internal node with midpoint mid, the invariant can be written as:

tree[left, right] = tree[left, mid] + tree[mid + 1, right]

The two child intervals are disjoint and together cover the entire parent interval. Therefore, adding their stored values produces the parent's range sum.

For the interval [0, 3]:

sum[0, 3] = sum[0, 1] + sum[2, 3]
         = 19 + 15
         = 34

For the root:

sum[0, 7] = sum[0, 3] + sum[4, 7]
         = 34 + 29
         = 63

The leaves establish the base values, and the internal nodes combine them. As long as this invariant is maintained, every stored interval sum can be trusted. A point update must therefore change the leaf and every ancestor whose interval contains that leaf.

The invariant also explains why a query can stop early. If the requested range completely contains a node's interval, the node already stores exactly the value needed for that interval.

4. Why the tree has logarithmic height​

At every internal level, an interval is divided into two smaller intervals. Starting with n positions, the interval lengths become approximately:

n, n / 2, n / 4, n / 8, ...

The number of halvings required to reach intervals of length one is proportional to log n. Therefore, the path from the root to any leaf has O(log n) nodes.

This height explains the update complexity directly. A point update follows one root-to-leaf path and then recomputes that same path on the way back. It does not need to inspect intervals that cannot contain the changed position.

The height also helps explain range queries. A query descends through only a logarithmic number of levels. It may visit both children at some levels, but it stops whenever an interval is fully covered or completely outside the requested range.

The complete tree contains O(n) nodes. There is one leaf for each array position, plus internal nodes that combine those leaves. In an implementation, the tree is often stored in an array rather than as objects linked by pointers. The logical binary-tree structure remains the same either way.

5. Building the tree​

The tree can be built recursively. A build operation receives a node and the interval [left, right] represented by that node.

There are two cases.

5.1 A leaf interval​

If left == right, the interval contains one position. The node receives the HP value from that array position:

build([3, 3]) = HP[3] = 5

A leaf does not need children because it already represents the smallest possible interval.

5.2 An internal interval​

If left < right, calculate a midpoint and create two child intervals:

mid = floor((left + right) / 2)
left child  = [left, mid]
right child = [mid + 1, right]

After both children have been built, combine their values:

node value = left child value + right child value

Pseudocode:

build(node, left, right):
    if left == right:
        tree[node] = HP[left]
        return

    mid = (left + right) // 2
    build(node * 2, left, mid)
    build(node * 2 + 1, mid + 1, right)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]

In the common array representation, the children of node node are stored at 2 * node and 2 * node + 1. The exact indexing convention may vary, especially if the root is stored at index 0 instead of index 1. The logical requirements do not change: every node must represent a known interval, and its value must equal the sum of that interval.

The build process visits the tree's nodes once, so its total time is O(n). The tree's storage requirement is O(n).

6. The three interval relationships in a query​

Suppose the game requests the sum over [queryLeft, queryRight]. At each node representing [left, right], compare the node interval with the query interval. There are three important relationships.

6.1 No overlap​

The intervals do not share any position:

node interval:  [0, 1]
query interval: [3, 5]

The node contributes nothing, so return the additive identity for sums:

0

There is no reason to visit the node's descendants. If the node has no overlap, none of its children can overlap either.

For inclusive intervals, a standard no-overlap condition is:

right < queryLeft or queryRight < left

6.2 Complete coverage​

The query interval completely contains the node interval:

node interval:  [2, 3]
query interval: [1, 6]

The entire node interval is needed. By the invariant, tree[node] is already the correct sum, so return it without descending further.

This is the key optimization. The query can use the stored total for a group of units instead of visiting each unit individually.

6.3 Partial overlap​

The intervals overlap, but neither completely contains the other:

node interval:  [0, 3]
query interval: [2, 5]

Only part of the node interval belongs to the query. The node's total cannot be used as a whole because it includes positions outside the requested range. Recurse into both children and combine the answers.

Pseudocode:

query(node, left, right, queryLeft, queryRight):
    if right < queryLeft or queryRight < left:
        return 0

    if queryLeft <= left and right <= queryRight:
        return tree[node]

    mid = (left + right) // 2
    leftSum = query(node * 2, left, mid, queryLeft, queryRight)
    rightSum = query(node * 2 + 1, mid + 1, right, queryLeft, queryRight)
    return leftSum + rightSum

The result is correct because the query combines a collection of disjoint tree intervals. Every requested position is included once, while positions outside the query are excluded.

7. Walking through a range query​

Use the sample array again:

[12, 7, 10, 5, 8, 6, 11, 4]

Ask for positions 2 through 5. The requested values are:

10, 5, 8, 6

At the root [0, 7], the query partially overlaps the interval. Split the root into [0, 3] and [4, 7].

On the left side:

  • [0, 1] has no overlap and contributes 0.
  • [2, 3] is completely covered and contributes its stored sum, 15.

On the right side:

  • [4, 5] is completely covered and contributes its stored sum, 14.
  • [6, 7] has no overlap and contributes 0.

The final answer is:

15 + 14 = 29

The query did not need to add all four individual values. It used the precomputed totals for [2, 3] and [4, 5].

The selected intervals do not have to be the same size. A query may combine a large completely covered interval with smaller intervals near the boundaries. For example, a range that begins or ends in the middle of a stored segment will descend only near that boundary and will use larger stored segments wherever possible.

8. Point updates: changing one unit's HP​

Now suppose the unit at position 3 changes from 5 HP to 9 HP. The array becomes:

[12, 7, 10, 9, 8, 6, 11, 4]

There are two common ways to describe this operation:

  1. Assignment: set the new HP to a specified value, such as HP[3] = 9.
  2. Delta update: add or subtract a change, such as +4 HP.

With assignment, the leaf is replaced by the new value. With a delta update, the leaf increases or decreases by the supplied amount. In both cases, the ancestors are recomputed.

For position 3, the recursive operation follows this path:

[0, 7]
  -> [0, 3]
      -> [2, 3]
          -> [3, 3]

At the leaf, replace 5 with 9. Then recompute while returning toward the root:

[2, 3] = 10 + 9 = 19
[0, 3] = 19 + 19 = 38
[0, 7] = 38 + 29 = 67

The right half [4, 7] remains 29 because position 3 is not part of that interval. The updated total for the battlefield is therefore 67.

Pseudocode for assignment is:

update(node, left, right, position, newHP):
    if left == right:
        tree[node] = newHP
        return

    mid = (left + right) // 2
    if position <= mid:
        update(node * 2, left, mid, position, newHP)
    else:
        update(node * 2 + 1, mid + 1, right, position, newHP)

    tree[node] = tree[node * 2] + tree[node * 2 + 1]

For a delta update, only the leaf operation changes:

addHP(node, left, right, position, delta):
    if left == right:
        tree[node] = tree[node] + delta
        return

    mid = (left + right) // 2
    if position <= mid:
        addHP(node * 2, left, mid, position, delta)
    else:
        addHP(node * 2 + 1, mid + 1, right, position, delta)

    tree[node] = tree[node * 2] + tree[node * 2 + 1]

The invariant after either operation is unchanged: every node still stores the sum of the current HP values in its interval.

9. Why a point update takes O(log n)​

A point update affects exactly one position. At every level of the tree, only one child contains that position. The update therefore follows one path from the root to one leaf.

The tree height is O(log n), so the number of visited nodes is O(log n). Recomputing an ancestor requires constant work: one addition of its two child sums. Consequently, the complete point update takes O(log n) time.

For example, changing position 3 affects these intervals:

[3, 3]
[2, 3]
[0, 3]
[0, 7]

It does not affect [4, 7], [4, 5], [6, 7], or any interval entirely to the right of position 3. Updating only the affected path is what avoids rebuilding all range totals.

10. Why a range query takes O(log n)​

A range query may visit both branches of the tree, but it does not visit every node. Large fully covered intervals stop the recursion early, and non-overlapping intervals are discarded immediately.

The query descends through O(log n) levels. Near the boundaries of the requested range, it may split into smaller pieces. Across the levels, only a logarithmic number of relevant segment boundaries need to be explored for the standard segment-tree range-sum query. This gives O(log n) time.

The main performance summary is:

build:        O(n)
range sum:    O(log n)
point update: O(log n)
space:        O(n)

If a program performs q queries and updates after construction, the total work is typically written as:

O(n + q log n)

The first term is the one-time build, and the second describes the repeated operations.

11. Choosing interval boundaries​

A practical implementation must decide whether intervals are inclusive or half-open. The examples in this article use inclusive intervals:

[left, right]

The interval [2, 5] contains positions 2, 3, 4, and 5. Its midpoint split is:

[left, mid]
[mid + 1, right]

Another valid convention is the half-open interval:

[left, right)

Under that convention, [2, 6) contains positions 2 through 5, and the split is commonly written as:

[left, mid)
[mid, right)

Neither convention is inherently better. Consistency is the important rule. The build, query, update, and midpoint logic must all use the same meaning for the endpoints.

Mixing conventions can cause several classic bugs:

  • the first or last position may be omitted;
  • a position may be counted twice;
  • a recursive interval may fail to become smaller;
  • a query may stop at the wrong boundary.

Writing down the interval convention before implementing the functions is a small step that prevents many errors.

12. Mapping game positions to array indexes​

Game descriptions may number units from 1 through n, while arrays in many programming languages use positions 0 through n - 1.

If the game sends a one-based position p, a zero-based implementation can convert it with:

internalPosition = p - 1

A one-based inclusive query from a through b becomes an internal query from a - 1 through b - 1.

The segment tree does not require one particular indexing system. It only requires that the positions used by input events and the positions used by the tree be mapped correctly. Boundary tests should include the first unit and the last unit because conversion errors often appear there first.

13. Assignment versus damage events​

Suppose a unit at position 5 takes 3 damage. If its current HP is 6, the new HP is 3. This event can be represented as a delta of -3.

If another event says that the unit's HP becomes 3, that is an assignment. These operations should not be confused:

add -3 to the current value
set the value to 3

They produce the same result in this particular example, but they have different meanings. A point-update interface should make the chosen meaning clear.

For a delta update, the leaf operation is addition. For an assignment update, the leaf operation is replacement. The path of affected ancestors and the O(log n) complexity are the same.

If the application receives relative damage or healing events, it may maintain the current HP array so that the new value can also be tracked directly. If each event supplies an absolute new HP value, the segment tree can receive that value at the leaf without needing a separate old-value lookup for the update itself.

14. Correctness reasoning​

The correctness of the data structure can be organized around its invariant.

Build correctness​

At a leaf, the stored value is exactly the HP at its one position. Assume the two children of an internal node correctly store the sums of their intervals. Since the parent interval is the disjoint union of those child intervals, adding the child values gives the correct parent sum. Applying this reasoning from leaves upward shows that every node is correct after construction.

Query correctness​

If a node has no overlap with the requested interval, returning 0 is correct because it contributes no positions. If the node is completely covered, returning its stored value is correct by the invariant. If the node partially overlaps, recursively querying both children partitions the relevant positions into child intervals. Adding their answers includes each requested HP exactly once and excludes every position outside the query.

Update correctness​

The update reaches the leaf representing the changed position and stores the new HP, or applies the supplied delta. Every ancestor on the path is then recomputed as the sum of its two children. Those ancestors become correct again. Nodes outside the path represent intervals that do not contain the changed position, so their sums do not need to change.

This reasoning shows why the segment tree continues to answer correct sums after any sequence of point updates.

15. A complete operation sequence​

Consider the following sequence:

Initial HP:       [12, 7, 10, 5, 8, 6, 11, 4]
Query [2, 5]:     29
Set position 3:   9
Query [2, 5]:     33

Before the update, the selected range is:

10 + 5 + 8 + 6 = 29

After setting position 3 to 9, the selected range becomes:

10 + 9 + 8 + 6 = 33

The update changes only one leaf and the ancestors that contain it. The next query automatically sees the refreshed totals because those nodes were recomputed during the update.

A query over the entire battlefield after the update reads the root and returns 67. A query over [4, 7] still returns 29 because that interval does not contain the changed position. This illustrates both sides of the invariant: affected intervals change, while disjoint intervals remain valid.

16. Single-position queries​

A range containing one position is simply a range sum of length one:

query(4, 4)

This returns the current HP at position 4 by following the tree to the corresponding leaf. The same query machinery handles both a single unit and a large region.

An application may also keep a direct HP array alongside the segment tree. That can be useful when game events need the old HP value or when other parts of the program need direct access to individual values. The segment tree's role is to maintain aggregate information efficiently; it does not prevent the application from storing the original point values as well.

17. Common implementation mistakes​

Updating only the leaf​

Changing the leaf without recomputing its ancestors leaves stale sums in the parent, grandparent, and root. Every recursive update must recompute the current node after the child update returns.

Returning the wrong value for no overlap​

For sums, a non-overlapping branch must return 0. This is the additive identity: adding zero does not alter the answer. Returning another value corrupts every query that skips a branch.

Using inconsistent overlap conditions​

For inclusive intervals, the no-overlap condition is:

right < queryLeft or queryRight < left

The complete-coverage condition is:

queryLeft <= left and right <= queryRight

Both tests must match the chosen boundary convention.

Splitting an inclusive interval incorrectly​

For [left, right], the usual split is:

[left, mid]
[mid + 1, right]

An update at position belongs to the left child when position <= mid; otherwise it belongs to the right child.

Confusing a position with an HP value​

The update position identifies the leaf to visit. The new HP or damage amount is the value associated with that leaf. Keeping these concepts separate prevents an update from changing the wrong location.

Forgetting one-based conversion​

If external positions start at 1 but the internal array starts at 0, subtract 1 when converting. Apply the same conversion consistently to both update positions and query endpoints.

Using an insufficient numeric type​

A range total can be much larger than one unit's HP because it combines many values. The chosen numeric type must be able to hold the largest possible sum allowed by the input. The exact type depends on the programming language and constraints.

18. Recursive and iterative representations​

The recursive form mirrors the tree definition and is often the easiest version to explain. Each function receives a node identifier and the interval represented by that node. The code follows the logical tree directly:

  • build splits an interval and combines child sums;
  • query applies the three overlap cases;
  • update follows one path and recomputes ancestors.

An iterative segment tree is another possible representation. It stores the leaves in one part of an array and computes parent sums while moving upward. A range query then moves inward from the two query boundaries, combining the appropriate stored segments.

Both styles implement the same invariant:

Each stored segment value is the sum of the HP values in that segment.

The recursive version makes interval relationships especially visible. The iterative version can be convenient when avoiding recursive calls or when the programming environment has a limited call stack. These are implementation choices; the standard complexity remains O(log n) for point updates and range sums.

19. When a segment tree is appropriate​

The battlefield HP problem is a natural fit because it combines four properties:

  1. values are arranged in a fixed order;
  2. queries cover contiguous ranges;
  3. individual positions can change;
  4. the required aggregate is addition.

If the program needed only one final total and no changes, a simple sum would be enough. If it needed range sums but never changed HP, a prefix-sum approach could answer ranges after preprocessing. However, point changes would make previously computed prefix totals stale. A segment tree maintains the aggregate information while changing only the intervals affected by an update.

The structure is therefore useful when the program must interleave operations such as:

range query
point update
range query
point update

The data structure does not scan an entire range for every query, and it does not rebuild every stored total after one local change.

20. Practical testing checklist​

Before relying on an implementation, test cases should cover both normal behavior and interval boundaries:

  • Build from a small array whose sums can be checked by hand.
  • Query the complete battlefield.
  • Query a single position.
  • Query a range that lies entirely in the left half.
  • Query a range that lies entirely in the right half.
  • Query a range crossing the midpoint.
  • Query a range that begins or ends at the battlefield boundary.
  • Update the first position.
  • Update the last position.
  • Update a position in the middle.
  • Query a range containing the changed position.
  • Query a range excluding the changed position.
  • Apply several updates to the same position.
  • Verify the root after each update against the sum of the current HP array.

For a small test array, comparing every segment-tree result with a direct loop is an effective way to check the implementation. The direct loop is not the efficient production method; it is simply a straightforward reference for testing.

21. Final perspective​

A segment tree turns the battlefield into a hierarchy of regions. Leaves represent individual units, while internal nodes represent totals for progressively larger contiguous intervals. The parent-child sum invariant gives every stored value a precise meaning.

A range-sum query compares the requested interval with each visited node. It ignores a non-overlapping interval, immediately uses a stored value for a completely covered interval, and splits a partially overlapping interval into its children. A point update reaches one leaf and refreshes the ancestors on that leaf's path.

Because the tree height is logarithmic, both required operations take O(log n) time. Building the tree takes O(n) time, and the structure uses O(n) space.

For a game that repeatedly asks for total HP in a region while individual units take damage or receive healing, the essential pattern is:

range sum    -> combine covered segment totals
point update -> change one leaf and recompute its ancestors

Once the interval boundaries and invariant are correct, the segment tree becomes a reliable way to maintain changing battlefield totals efficiently.