CPP notes

Some Terms In-place Sorting => use constant space to sort (modify only the given array) Stable sorting - When two same values appear in the same relative order in sorted data as in the original array => Eg: Merge Sort, Insertion Sort, Bubble Sort ₪ When equal elements are indistinguishable like integers => stability is not an issue.         →    ----> If stable sorting is used => get shown pic ₪   If we sort section-wise & sorting algorithm is unstable => may get random ordering ₪  Any given sorting algorithm which is unstable can be modified to be stable     Augment index along with value → If values are same  → use index as tiebreaker → Drawback - extra O(N) space to store index for N element + need extra comparison Counting sort is unstable but can be made stable - 1 6a 8 3 6b 0 6c 4 ---> a, b, c is used just to distinguish ordering of same value Stable Algo - 0 1 3 4 6a 6b 6c 8 count arr...

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link