Back to Repositories

Testing Segment Tree Sum Query Operations with Multiplication Updates in Algorithms

This test suite validates the implementation of a Segment Tree data structure specialized for sum queries with multiplication updates in Java. It thoroughly examines the functionality of range-based operations and ensures correct handling of numerical computations across segments.

Test Coverage Overview

The test suite provides comprehensive coverage of the SumQueryMultiplicationUpdateSegmentTree implementation:

Simple test cases validating basic range updates and queries
Randomized testing with varying array sizes and range operations
Edge cases handling for array bounds and numerical operations
Verification of multiplication-based updates across ranges

Implementation Analysis

The testing approach employs both deterministic and randomized testing strategies using JUnit 5 framework. It implements brute force methods as reference implementations to verify the segment tree’s correctness.

Parallel verification using brute force methods
Randomized test data generation
Iterative testing with multiple array sizes

Technical Details

Testing infrastructure includes:

JUnit Jupiter (JUnit 5) as the testing framework
Google Truth for assertions
Custom TestUtils for random data generation
Gradle test runner configuration
BeforeEach setup methods for test initialization

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Separation of concerns between test cases
Comprehensive validation using both simple and complex scenarios
Robust comparison with brute force implementation
Clear test method naming and organization
Proper test setup and initialization patterns

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/segmenttree/SumQueryMultiplicationUpdateSegmentTreeTest.java

            
/**
 * gradle test --info --tests
 * "com.williamfiset.algorithms.datastructures.segmenttree.SumQueryMultiplicationUpdateSegmentTreeTest"
 */
package com.williamfiset.algorithms.datastructures.segmenttree;

import static com.google.common.truth.Truth.assertThat;

import com.williamfiset.algorithms.utils.TestUtils;
import org.junit.jupiter.api.*;

public class SumQueryMultiplicationUpdateSegmentTreeTest {

  static int ITERATIONS = 100;
  static int MAX_N = 28;

  @BeforeEach
  public void setup() {}

  @Test
  public void simpleTest() {
    long[] ar = {1, 4, 5, 3, 2};
    SumQueryMultiplicationUpdateSegmentTree st = new SumQueryMultiplicationUpdateSegmentTree(ar);

    st.rangeUpdate1(1, 3, 3);

    assertThat(st.rangeQuery1(1, 3)).isEqualTo(4 * 3 + 5 * 3 + 3 * 3);
    assertThat(st.rangeQuery1(0, 4)).isEqualTo(1 + 4 * 3 + 5 * 3 + 3 * 3 + 2);
    assertThat(st.rangeQuery1(0, 2)).isEqualTo(1 + 4 * 3 + 5 * 3);
    assertThat(st.rangeQuery1(2, 4)).isEqualTo(5 * 3 + 3 * 3 + 2);

    st.rangeUpdate1(1, 3, 2);
    assertThat(st.rangeQuery1(1, 3)).isEqualTo(4 * 3 * 2 + 5 * 3 * 2 + 3 * 3 * 2);
  }

  @Test
  public void testRandomRangeSumUpdatesWithSumRangeQueries() {
    for (int n = 5; n < MAX_N; n++) {
      long[] ar = TestUtils.randomLongArray(n, -10, +10);
      SumQueryMultiplicationUpdateSegmentTree st =
          new SumQueryMultiplicationUpdateSegmentTree(ar.clone());

      for (int i = 0; i < ITERATIONS; i++) {
        int j = TestUtils.randValue(0, n - 1);
        int k = TestUtils.randValue(0, n - 1);
        int i1 = Math.min(j, k);
        int i2 = Math.max(j, k);

        j = TestUtils.randValue(0, n - 1);
        k = TestUtils.randValue(0, n - 1);
        int i3 = Math.min(j, k);
        int i4 = Math.max(j, k);

        // Range update.
        // Yes, these values will likely cause overflow through excessive
        // multiplication of segment values
        long randValue = TestUtils.randValue(-100, +100);
        bruteForceMulRangeUpdate(ar, i3, i4, randValue);
        st.rangeUpdate1(i3, i4, randValue);

        // Range query
        long bfSum = bruteForceSum(ar, i1, i2);
        long segTreeSum = st.rangeQuery1(i1, i2);
        assertThat(bfSum).isEqualTo(segTreeSum);
      }
    }
  }

  // Finds the sum in an array between [l, r] in the `values` array
  private static long bruteForceSum(long[] values, int l, int r) {
    long s = 0;
    for (int i = l; i <= r; i++) {
      s += values[i];
    }
    return s;
  }

  // Finds the min value in an array between [l, r] in the `values` array
  private static long bruteForceMin(long[] values, int l, int r) {
    long m = values[l];
    for (int i = l; i <= r; i++) {
      m = Math.min(m, values[i]);
    }
    return m;
  }

  // Finds the max value in an array between [l, r] in the `values` array
  private static long bruteForceMax(long[] values, int l, int r) {
    long m = values[l];
    for (int i = l; i <= r; i++) {
      m = Math.max(m, values[i]);
    }
    return m;
  }

  private static void bruteForceSumRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] += x;
    }
  }

  private static void bruteForceMulRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] *= x;
    }
  }

  private static void bruteForceAssignRangeUpdate(long[] values, int l, int r, long x) {
    for (int i = l; i <= r; i++) {
      values[i] = x;
    }
  }
}