线段树任务的问题

Question

我需要编写程序，有效地找到给定段上最长的连续零序列的长度

[l, r]

，并根据要求更新该值。 (

UPDATE

)

我有这个代码：

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

public class algo1c_2 {
    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[] buildTree(int[] data) {
        int n = data.length;
        treeLeaf[] tree = new treeLeaf[2 * n];
        for (int i = 0; i < n; i++) {
            if (data[i] == 0) {
                tree[n + i] = new treeLeaf(1, 1, 1, 1);
            } else {
                tree[n + i] = new treeLeaf(0, 0, 0, 1);
            }
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
        return tree;
    }

    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 void update(int[] data, treeLeaf[] tree, int pos, int newValue, int n) {
        pos += n;
        data[pos - n] = newValue;
        if (newValue == 0) {
            tree[pos] = new treeLeaf(1, 1, 1, 1);
        } else {
            tree[pos] = new treeLeaf(0, 0, 0, 1);
        }

        while (pos > 1) {
            pos /= 2;
            tree[pos] = merge(tree[2 * pos], tree[2 * pos + 1]);
        }
    }

    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;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(in.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(in.readLine());

        for (int i = 0; i < n; i++) {
            if (!st.hasMoreTokens()) st = new StringTokenizer(in.readLine());
            a[i] = Integer.parseInt(st.nextToken());
        }

        treeLeaf[] tree = buildTree(a);

        int k = Integer.parseInt(in.readLine());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(in.readLine());
            String type = st.nextToken();

            if (Objects.equals(type, "QUERY")) {
                int l = Integer.parseInt(st.nextToken()) - 1;
                int r = Integer.parseInt(st.nextToken()) - 1;
                treeLeaf ans = rmq(l, r, tree);
                out.write(ans.maxSeq + "\n");
            } else if (Objects.equals(type, "UPDATE")) {
                int pos = Integer.parseInt(st.nextToken()) - 1;
                int newVal = Integer.parseInt(st.nextToken());
                update(a, tree, pos, newVal, n);
            }
        }
        in.close();
        out.flush();
        out.close();
    }
}

但是当我运行测试时：

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

我的程序打印

5

而不是

4

。我怀疑问题出在函数

merge

上，但我没有看到它......

Answer 1

您的

merge

方法不可交换，因此您不能以任意顺序合并。对于此版本的线段树，您可以将左侧的所有结果与右侧的结果分开合并，然后将这两个结果合并为循环后的最终答案。

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(rightRes, tree[r--]);
    }
    return merge(leftRes, rightRes);
}