Practical decisions

Use a Fenwick tree when the operation has an inverse (sum, XOR, counting) and you only need point updates with prefix or range queries. It is shorter, faster in practice, and uses n + 1 cells. Use a segment tree when the operation has no inverse (minimum, maximum, GCD), when you need range updates with lazy propagation, or when the node must store a structure (maximum subarray, sorted lists).

For range add with range sum, a Fenwick pair works and is simple; for range assign, or add with minimum, you need a lazy segment tree. When in doubt, ask two questions: can the answer for a range be computed from the answer for the prefixes (then Fenwick), and does an update change the whole range at once (then lazy)?

1int[] bit = new int[n + 1];                          // 1-based: bit[i] covers the lowbit(i) values ending at i
2void update(int i, int delta) {                      // a[i] += delta, i is 1-based
3    for (; i <= n; i += i & -i) bit[i] += delta;     // climb: add the lowest set bit
4}
5int prefix(int i) {                                  // sum of a[1..i]
6    int s = 0;
7    for (; i > 0; i -= i & -i) s += bit[i];          // descend: strip the lowest set bit
8    return s;
9}
10int range(int l, int r) { return prefix(r) - prefix(l - 1); }
11void buildLinear(int[] a) {                          // O(n) build
12    for (int i = 1; i <= n; i++) {
13        bit[i] += a[i];
14        int j = i + (i & -i);                        // the next cell that covers i
15        if (j <= n) bit[j] += bit[i];
16    }
17}

A Fenwick tree needs n + 1 cells. A recursive segment tree has 2n - 1 nodes but, stored by heap index, needs an array big enough for the largest index in use. Sizing it as 4n is always safe. A tighter safe size is twice the next power of two above n, which is at most 4n - 2 and often much smaller. A bottom-up segment tree needs exactly 2n cells, because leaves go at n..2n-1.

Lazy trees need extra arrays for the tags (one per tag field), and merge-sort trees need O(n log n) cells. Persistent trees add O(log n) nodes per update and dynamic trees O(log size) nodes per touched position. When memory is tight, use the smallest layout that supports your operations: 2n iterative, then 2 × next power of two recursive, then 4n.

1static int nextPowerOfTwo(int n) { return n <= 1 ? 1 : Integer.highestOneBit(n - 1) << 1; }
2static int recursiveTreeSize(int n) { return 2 * nextPowerOfTwo(n); }    // enough for every heap index of the recursive split
3static int iterativeTreeSize(int n) { return 2 * n; }
4static int fenwickSize(int n) { return n + 1; }

The **bottom-up** segment tree stores the leaves at positions n..2n-1 and every inner node i as the combination of 2i and 2i + 1. A point update sets the leaf and walks up by halving the index. A range query on the half-open interval [l, r) moves both ends up one level at a time: if l is a right child, its node is part of the answer and l moves right; if r is a right child, the node to its left is part of the answer. There is no recursion and the array has exactly 2n cells.

For a non-commutative operation keep two accumulators: the nodes taken at the left end go to the left result in increasing position order, and the nodes taken at the right end are prepended to the right result. The final answer is left combined with right. Compare with the animation's "Iterative sum" preset: the query [1, 4] on 2 5 1 4 9 3 takes 3 nodes and returns 19.

1class IterativeSegmentTree {
2    private final int n;
3    private final long[] t;
4    private final LongBinaryOperator op;
5    private final long identity;
6    IterativeSegmentTree(int[] a, LongBinaryOperator op, long identity) {
7        this.n = a.length; this.op = op; this.identity = identity;
8        t = new long[2 * n];
9        for (int i = 0; i < n; i++) t[n + i] = a[i];
10        for (int i = n - 1; i >= 1; i--) t[i] = op.applyAsLong(t[2 * i], t[2 * i + 1]);
11    }
12    void set(int i, long v) {
13        for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = op.applyAsLong(t[i & ~1], t[i | 1]);   // left child first
14    }
15    long query(int l, int r) {                   // half-open [l, r); correct for non-commutative operations
16        long left = identity, right = identity;
17        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
18            if ((l & 1) == 1) left = op.applyAsLong(left, t[l++]);     // append on the left side
19            if ((r & 1) == 1) right = op.applyAsLong(t[--r], right);   // prepend on the right side
20        }
21        return op.applyAsLong(left, right);
22    }
23}

1void build(int node, int lo, int hi) {                   // recursive segment tree
2    if (lo == hi) { tree[node] = a[lo]; return; }        // leaf
3    int mid = lo + (hi - lo) / 2;
4    build(2 * node, lo, mid);
5    build(2 * node + 1, mid + 1, hi);
6    tree[node] = tree[2 * node] + tree[2 * node + 1];     // combine
7}
8int query(int node, int lo, int hi, int l, int r) {
9    if (r < lo || hi < l) return 0;                       // disjoint: the neutral element
10    if (l <= lo && hi <= r) return tree[node];            // fully inside: use the stored value
11    int mid = lo + (hi - lo) / 2;
12    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
13}
14void update(int node, int lo, int hi, int i, int v) {
15    if (lo == hi) { tree[node] = v; return; }
16    int mid = lo + (hi - lo) / 2;
17    if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
18    tree[node] = tree[2 * node] + tree[2 * node + 1];     // recompute on the way back
19}
20int queryIterative(int l, int r) {                        // bottom-up, half-open [l, r)
21    int res = 0;
22    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
23        if ((l & 1) == 1) res += tree[l++];               // l is a right child: take it and move right
24        if ((r & 1) == 1) res += tree[--r];               // r is exclusive: its left neighbour is a right child
25    }
26    return res;
27}

Three conventions meet in this chapter: Fenwick trees are 1-based, most Java arrays and segment trees are 0-based, and the iterative segment tree and String.substring use half-open ranges [l, r). Convert once, at the boundary, and keep everything inside the structure in one convention. A wrapper class that exposes 0-based inclusive ranges, as most problem statements do, removes the whole class of off-by-one bugs from the calling code.

The usual conversions: 0-based index i is Fenwick position i + 1; an inclusive [l, r] is the half-open [l, r + 1); and sum(l..r) = prefix(r + 1) - prefix(l) when prefix(e) means the sum of the first e elements. With these, l = 0 needs no special case, because prefix(0) is an empty sum.

1class ZeroBasedFenwick {                         // 0-based, inclusive ranges, like most problem statements
2    private final long[] tree;
3    ZeroBasedFenwick(int n) { tree = new long[n + 1]; }
4    void add(int index, long delta) {
5        for (int i = index + 1; i < tree.length; i += i & -i) tree[i] += delta;      // 0-based -> 1-based
6    }
7    long prefix(int endExclusive) {              // sum of [0, endExclusive)
8        long s = 0;
9        for (int i = endExclusive; i > 0; i -= i & -i) s += tree[i];
10        return s;
11    }
12    long sum(int l, int r) { return prefix(r + 1) - prefix(l); }       // inclusive [l, r]
13}

Range structures break at the edges, so test those on purpose, against a brute-force array. The important cases: a single element (l == r), the first element, the last element, the whole array, n = 1, n a power of two and n one more or one less than a power of two, updates at the first and last index, and an update that does not change the value. Then add randomised operations: random updates and random ranges, compared with a plain loop after every step.

The harness below drives any structure that implements a tiny interface, so the same test checks a Fenwick wrapper, a segment tree or a lazy tree. Failures print the first operation that disagrees, which is usually enough to see the bug. Run it for several sizes, not only one: many bugs appear only when n is odd or a power of two.

1interface RangeSum {
2    void set(int i, long v);                     // a[i] = v, 0-based
3    long sum(int l, int r);                      // inclusive, 0-based
4}
5static String stress(RangeSum fast, int n, int rounds, long seed) {
6    Random rnd = new Random(seed);
7    long[] a = new long[n];
8    for (int round = 0; round < rounds; round++) {
9        int i = rnd.nextInt(n);
10        long v = rnd.nextInt(2001) - 1000;
11        a[i] = v;
12        fast.set(i, v);
13        int l = rnd.nextInt(n), r = rnd.nextInt(n);
14        if (l > r) { int t = l; l = r; r = t; }
15        int[][] ranges = {{l, r}, {0, n - 1}, {0, 0}, {n - 1, n - 1}, {i, i}};      // random, whole, first, last, changed
16        for (int[] q : ranges) {
17            long want = 0;
18            for (int k = q[0]; k <= q[1]; k++) want += a[k];
19            if (fast.sum(q[0], q[1]) != want)
20                return "sum(" + q[0] + ", " + q[1] + ") after set(" + i + ", " + v + "): expected " + want;
21        }
22    }
23    return "ok";
24}