Generic Segment Tree Min/Max range update bugs

[williamfiset]

The generic segment tree implementation seems to be suffering from two issues when using multiplication range updates with min/max range queries:

• The segment tree doesn't seem to handle overflow well (hard to avoid with multiplication updates in general), or at least the result doesn't match with the test values. This may be because the segment tree only capture the min/max value in a segment and when this value overflows the true min/max is lost -- not sure how much can be done here. Perhaps just ensure no overflow can happen in the tests?

• Updates involving negative values aren't being handled. I'm not certain this can be handled with the current framework -- I think we may need to keep track of more information. It may be worth investigating if a shadow min segment tree (or a pair of values on the segment node) can be useful for a max segment tree for this situation (and vice versa) when we encounter a negative value. My idea is that for a max segment tree when a negative value is encountered, the maximum value would become the minimum value in a min segment tree -- i don't know if this works, but I think it's in the right direction.

    long[] ar = {2, 1, 3, 4, -1};
    GenericSegmentTree st =
        new GenericSegmentTree(
            ar,
            GenericSegmentTree.SegmentCombinationFn.MAX,
            GenericSegmentTree.RangeUpdateFn.MULTIPLICATION);

    st.rangeUpdate1(0, 4, 1);
    assertThat(st.rangeQuery1(0, 4)).isEqualTo(4);

    // Negative numbers are a known issue
    st.rangeUpdate1(0, 4, -2);
    assertThat(st.rangeQuery1(0, 4)).isEqualTo(2); // Returns -8 as max but should be 2