🚀 Advanced Algorithms

// Merge Sort - Classic Divide & Conquer, O(n log n)
function mergeSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = []; $i = 0; $j = 0;
    while ($i < count($left) && $j < count($right)) {
        $result[] = $left[$i] <= $right[$j] ? $left[$i++] : $right[$j++];
    }
    return [...$result, ...array_slice($left,$i), ...array_slice($right,$j)];
}

// Essential bit operations - O(1) each
$x = 5; // 0101

echo $x & 1;     // 1 (check if odd: LSB is 1)
echo $x >> 1;    // 2 (divide by 2, shift right)
echo $x << 1;    // 10 (multiply by 2, shift left)
echo $x & ($x-1);// 4 (clear lowest set bit: 0101→0100)
echo $x & -$x;   // 1 (isolate lowest set bit)

// Count set bits (Brian Kernighan's algorithm)
function countSetBits(int $n): int {
    $count = 0;
    while ($n) { $n &= ($n-1); $count++; }
    return $count;
}

// Check if power of 2
function isPowerOfTwo(int $n): bool {
    return $n > 0 && ($n & ($n-1)) === 0;
}

// Generate all subsets of n elements using bitmask
function subsetsBitmask(array $arr): array {
    $n = count($arr); $result = [];
    for ($mask = 0; $mask < (1 << $n); $mask++) {
        $subset = [];
        for ($i = 0; $i < $n; $i++) {
            if ($mask & (1 << $i)) $subset[] = $arr[$i];
        }
        $result[] = $subset;
    }
    return $result;
}

// Maximum sum of subarray of size k - O(n)
function maxSumSubarray(array $arr, int $k): int {
    $n = count($arr);
    if ($n < $k) return -1;

    // First window sum
    $windowSum = array_sum(array_slice($arr, 0, $k));
    $maxSum = $windowSum;

    // Slide window
    for ($i = $k; $i < $n; $i++) {
        $windowSum += $arr[$i] - $arr[$i - $k];
        $maxSum = max($maxSum, $windowSum);
    }
    return $maxSum;
}

// Longest substring without repeating characters - O(n)
function lengthOfLongestSubstring(string $s): int {
    $n = strlen($s); $maxLen = 0;
    $left = 0; $seen = [];

    for ($right = 0; $right < $n; $right++) {
        $char = $s[$right];
        if (isset($seen[$char]) && $seen[$char] >= $left) {
            $left = $seen[$char] + 1;
        }
        $seen[$char] = $right;
        $maxLen = max($maxLen, $right - $left + 1);
    }
    return $maxLen;
}

// Find pair with target sum in sorted array - O(n)
function twoSumSorted(array $arr, int $target): array {
    $left = 0; $right = count($arr) - 1;
    while ($left < $right) {
        $sum = $arr[$left] + $arr[$right];
        if ($sum === $target) return [$left, $right];
        if ($sum < $target) $left++;
        else $right--;
    }
    return [];
}

// Remove duplicates in-place from sorted array - O(n)
function removeDuplicates(array &$arr): int {
    $n = count($arr); if ($n <= 1) return $n;
    $writeIndex = 1; // position to write next unique
    for ($i = 1; $i < $n; $i++) {
        if ($arr[$i] !== $arr[$i-1]) {
            $arr[$writeIndex++] = $arr[$i];
        }
    }
    return $writeIndex; // new length
}

// Range Sum Query - O(log n) update & query
class SegmentTree {
    private array $tree; private int $n;

    public function __construct(array $arr) {
        $this->n = count($arr);
        $this->tree = array_fill(0, 4 * $this->n, 0);
        $this->build($arr, 0, 0, $this->n - 1);
    }

    private function build(array &$arr, int $node, int $start, int $end): void {
        if ($start === $end) {
            $this->tree[$node] = $arr[$start];
        } else {
            $mid = intdiv($start + $end, 2);
            $this->build($arr, 2*$node+1, $start, $mid);
            $this->build($arr, 2*$node+2, $mid+1, $end);
            $this->tree[$node] = $this->tree[2*$node+1] + $this->tree[2*$node+2];
        }
    }

    public function query(int $l, int $r): int {
        return $this->queryRec(0, 0, $this->n-1, $l, $r);
    }

    private function queryRec(int $node, int $start, int $end, int $l, int $r): int {
        if ($r < $start || $l > $end) return 0;     // No overlap
        if ($l <= $start && $end <= $r) return $this->tree[$node]; // Full overlap
        $mid = intdiv($start + $end, 2);
        return $this->queryRec(2*$node+1,$start,$mid,$l,$r)
             + $this->queryRec(2*$node+2,$mid+1,$end,$l,$r);
    }

    public function update(int $idx, int $val): void {
        $this->updateRec(0, 0, $this->n-1, $idx, $val);
    }
    // ... updateRec implementation
}