Issue with segment tree task

Question

I need to write a program that efficiently finds the length of the longest continuous sequence of zeroes on the given segment [l, r] (a particular subarray) and updates the value if requested, both operations in logarithmic time.

I have this code:

import java.io.*;
import java.util.Objects;
import java.util.StringTokenizer;

public class task {
    static class treeLeaf {
        int maxSeq;
        int prefSeq;
        int suffSeq;
        int length;

        treeLeaf(int maxSeq, int prefSeq, int suffSeq, int length) {
            this.maxSeq = maxSeq;
            this.prefSeq = prefSeq;
            this.suffSeq = suffSeq;
            this.length = length;
        }
    }

    static treeLeaf merge(treeLeaf left, treeLeaf right) {
        int maxSeq = Math.max(left.maxSeq, right.maxSeq);
        if (left.suffSeq > 0 && right.prefSeq > 0) {
            maxSeq = Math.max(maxSeq, left.suffSeq + right.prefSeq);
        }

        int prefSeq = left.prefSeq;
        if (left.prefSeq == left.length) {
            prefSeq += right.prefSeq;
        }

        int suffSeq = right.suffSeq;
        if (right.suffSeq == right.length) {
            suffSeq += left.suffSeq;
        }

        return new treeLeaf(maxSeq, prefSeq, suffSeq, left.length + right.length);
    }

    static treeLeaf rmq(int l, int r, treeLeaf[] tree) {
        int n = tree.length / 2;
        l += n;
        r += n;
        treeLeaf res = new treeLeaf(0, 0, 0, 0);

        while (l <= r) {
            if ((l & 1) == 1) {
                res = merge(res, tree[l]);
                l++;
            }
            if ((r & 1) == 0) {
                res = merge(res, tree[r]);
                r--;
            }
            if (l > r) break;
            l /= 2;
            r /= 2;
        }
        return res;
    }
}

But when I run test:

18
6 0 0 1 0 0 0 0 2 4 5 6 9 0 0 0 0 1
1
QUERY 1 18

My program prints 5 instead of 4. I suspect that issue is with function merge, but I don't see it...

Answer 1

Your merge method is not commutative, so you cannot merge in an arbitrary order. For this version of the segment tree, you can merge all the results on the left side separately from the results on the right side, then merge these two results for the final answer after the loop.

static treeLeaf rmq(int l, int r, treeLeaf[] tree) {
    int n = tree.length / 2;
    treeLeaf leftRes = new treeLeaf(0, 0, 0, 0), rightRes = new treeLeaf(0, 0, 0, 0);
    for (l += n, r += n; l <= r; l /= 2, r /= 2) {
        if ((l & 1) == 1) leftRes = merge(leftRes, tree[l++]);
        if ((r & 1) == 0) rightRes = merge(tree[r--], rightRes);
    }
    return merge(leftRes, rightRes);
}