Unit 19 — Advanced Topics

You have an array and need to answer many queries like "what is the sum of elements from index 3 to 7?" or "what is the minimum between index 2 and 9?" If the array never changes, prefix sums handle this in O(1). But if the array gets updated frequently, prefix sums become O(n) per update. A Segment Tree does both — query AND update — in O(log n).

#include <stdio.h>
 
#define MAXN 100
int seg[4 * MAXN];  /* segment tree array — needs 4x the input size */
 
/* build the segment tree */
void build(int arr[], int node, int start, int end) {
    if (start == end) {
        seg[node] = arr[start];  /* leaf: store the element itself */
        return;
    }
    int mid = (start + end) / 2;
    build(arr, 2*node,   start, mid);    /* build left child */
    build(arr, 2*node+1, mid+1, end);    /* build right child */
    seg[node] = seg[2*node] + seg[2*node+1];  /* internal: sum of children */
}
 
/* range sum query: sum of arr[l..r] */
int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;   /* range completely outside */
    if (l <= start && end <= r) return seg[node];  /* range completely inside */
 
    int mid = (start + end) / 2;
    int leftSum  = query(2*node,   start, mid,   l, r);
    int rightSum = query(2*node+1, mid+1, end,   l, r);
    return leftSum + rightSum;
}
 
/* point update: set arr[idx] = val */
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        seg[node] = val;  /* update the leaf */
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2*node,   start, mid,   idx, val);
    else            update(2*node+1, mid+1, end,   idx, val);
    seg[node] = seg[2*node] + seg[2*node+1];  /* recompute internal node */
}
 
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 6;
 
    build(arr, 1, 0, n-1);
 
    printf("Sum [1..3]: %d\n", query(1, 0, n-1, 1, 3));  /* 3+5+7 = 15 */
    printf("Sum [0..5]: %d\n", query(1, 0, n-1, 0, 5));  /* 1+3+5+7+9+11 = 36 */
 
    update(1, 0, n-1, 1, 10);  /* set arr[1] = 10 (was 3) */
    printf("Sum [1..3] after update: %d\n", query(1, 0, n-1, 1, 3));  /* 10+5+7 = 22 */
 
    return 0;
}

A Binary Indexed Tree (BIT or Fenwick Tree) is a simpler alternative to the Segment Tree for prefix sum queries with point updates. It uses a clever trick with the lowest set bit of an index to navigate the tree implicitly — no explicit tree structure needed. The code is remarkably short for what it does.

#include <stdio.h>
 
#define MAXN 100
int bit[MAXN + 1];  /* 1-indexed */
int n;
 
/* get the lowest set bit of i */
/* e.g. lowbit(6) = lowbit(110₂) = 010₂ = 2 */
int lowbit(int i) { return i & (-i); }
 
/* point update: add delta to position i */
void updateBIT(int i, int delta) {
    for (; i <= n; i += lowbit(i)) {
        bit[i] += delta;
    }
}
 
/* prefix sum query: sum of arr[1..i] */
int queryBIT(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) {
        sum += bit[i];
    }
    return sum;
}
 
/* range sum query: sum of arr[l..r] */
int rangeQuery(int l, int r) {
    return queryBIT(r) - queryBIT(l - 1);
}
 
int main() {
    int arr[] = {0, 1, 3, 5, 7, 9, 11};  /* 1-indexed, arr[0] unused */
    n = 6;
    int i;
 
    /* build BIT from array */
    for (i = 1; i <= n; i++) updateBIT(i, arr[i]);
 
    printf("Prefix sum [1..3]: %d\n", queryBIT(3));       /* 1+3+5 = 9 */
    printf("Range sum  [2..5]: %d\n", rangeQuery(2, 5));  /* 3+5+7+9 = 24 */
 
    updateBIT(2, 7);  /* add 7 to position 2: arr[2] becomes 3+7=10 */
    printf("After update, range [2..5]: %d\n", rangeQuery(2, 5)); /* 10+5+7+9 = 31 */
 
    return 0;
}

A Trie is a tree where each path from root to a node spells a string. Every character of a word occupies one node. Words that share a prefix share the same path from the root. Insert, search, and prefix-check all run in O(L) where L is the string length — independent of how many strings are stored. Google search suggestions, phone autocomplete, and dictionary lookups all use tries.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define ALPHA 26  /* 26 lowercase letters */
 
struct TrieNode {
    struct TrieNode *children[ALPHA];
    int isEnd;  /* 1 if this node marks end of a word */
};
typedef struct TrieNode TrieNode;
 
TrieNode* newNode() {
    TrieNode *node = calloc(1, sizeof(TrieNode));
    node->isEnd = 0;
    return node;
}
 
/* insert a word into the trie */
void insert(TrieNode *root, char *word) {
    TrieNode *current = root;
    int i;
    for (i = 0; word[i]; i++) {
        int idx = word[i] - 'a';  /* 'a'=0, 'b'=1, ... 'z'=25 */
        if (!current->children[idx]) {
            current->children[idx] = newNode();
        }
        current = current->children[idx];
    }
    current->isEnd = 1;  /* mark end of word */
}
 
/* search: returns 1 if exact word exists */
int search(TrieNode *root, char *word) {
    TrieNode *current = root;
    int i;
    for (i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!current->children[idx]) return 0;  /* character not found */
        current = current->children[idx];
    }
    return current->isEnd;  /* 1 only if a complete word ends here */
}
 
/* startsWith: returns 1 if any word starts with given prefix */
int startsWith(TrieNode *root, char *prefix) {
    TrieNode *current = root;
    int i;
    for (i = 0; prefix[i]; i++) {
        int idx = prefix[i] - 'a';
        if (!current->children[idx]) return 0;
        current = current->children[idx];
    }
    return 1;  /* prefix exists */
}
 
int main() {
    TrieNode *root = newNode();
 
    insert(root, "cat");
    insert(root, "can");
    insert(root, "car");
    insert(root, "bat");
    insert(root, "bad");
 
    printf("Search 'cat':    %d\n", search(root, "cat"));      /* 1 */
    printf("Search 'ca':     %d\n", search(root, "ca"));       /* 0 — not a word */
    printf("Prefix 'ca':     %d\n", startsWith(root, "ca"));   /* 1 — prefix exists */
    printf("Prefix 'xyz':    %d\n", startsWith(root, "xyz"));  /* 0 */
    printf("Search 'dog':    %d\n", search(root, "dog"));      /* 0 */
 
    return 0;
}

Union-Find (also called Disjoint Set Union, DSU) maintains a collection of disjoint sets and supports two operations: union (merge two sets) and find (which set does an element belong to). With path compression and union by rank, both operations run in nearly O(1) amortised time. Used in Kruskal's MST, network connectivity, and image segmentation.

#include <stdio.h>
 
#define MAXN 100
int parent[MAXN];
int rank_arr[MAXN];  /* rank for union by rank */
 
/* initialise: each element is its own parent */
void initDSU(int n) {
    int i;
    for (i = 0; i < n; i++) {
        parent[i] = i;   /* each node is its own root */
        rank_arr[i] = 0;
    }
}
 
/* find: returns the root of x's set — with PATH COMPRESSION */
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  /* compress: point directly to root */
    }
    return parent[x];
}
 
/* union: merge the sets containing x and y — UNION BY RANK */
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;  /* already in same set */
 
    /* attach smaller tree under larger tree */
    if (rank_arr[rootX] < rank_arr[rootY]) {
        parent[rootX] = rootY;
    } else if (rank_arr[rootX] > rank_arr[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank_arr[rootX]++;  /* same rank — increase rank of new root */
    }
}
 
/* check if x and y are in the same set */
int connected(int x, int y) {
    return find(x) == find(y);
}
 
int main() {
    initDSU(6);  /* 6 elements: 0 to 5 */
 
    unite(0, 1);  /* {0,1}, {2}, {3}, {4}, {5} */
    unite(1, 2);  /* {0,1,2}, {3}, {4}, {5} */
    unite(3, 4);  /* {0,1,2}, {3,4}, {5} */
 
    printf("0 and 2 connected: %d\n", connected(0, 2)); /* 1 — yes */
    printf("0 and 3 connected: %d\n", connected(0, 3)); /* 0 — no */
    printf("3 and 4 connected: %d\n", connected(3, 4)); /* 1 — yes */
 
    unite(2, 3);  /* {0,1,2,3,4}, {5} */
    printf("0 and 4 connected: %d\n", connected(0, 4)); /* 1 — now yes */
 
    return 0;
}

Many problems ask: "find the subarray of size k with the maximum sum" or "find the smallest subarray with sum ≥ target." A naive approach checks all subarrays in O(n²). The sliding window technique maintains a window that slides across the array — expanding and contracting as needed — in a single O(n) pass.

#include <stdio.h>
 
/* FIXED WINDOW: max sum subarray of size k */
int maxSumFixed(int arr[], int n, int k) {
    int windowSum = 0, maxSum, i;
 
    /* compute sum of first window */
    for (i = 0; i < k; i++) windowSum += arr[i];
    maxSum = windowSum;
 
    /* slide the window */
    for (i = k; i < n; i++) {
        windowSum += arr[i];       /* add new right element */
        windowSum -= arr[i - k];   /* remove old left element */
        if (windowSum > maxSum) maxSum = windowSum;
    }
    return maxSum;
}
 
/* VARIABLE WINDOW: smallest subarray with sum >= target */
int smallestSubarray(int arr[], int n, int target) {
    int minLen = n + 1;
    int left = 0, sum = 0, right;
 
    for (right = 0; right < n; right++) {
        sum += arr[right];  /* expand window to the right */
 
        /* shrink from left while sum still >= target */
        while (sum >= target) {
            int len = right - left + 1;
            if (len < minLen) minLen = len;
            sum -= arr[left];
            left++;
        }
    }
    return minLen == n + 1 ? -1 : minLen;
}
 
int main() {
    int arr1[] = {2, 1, 5, 1, 3, 2};
    printf("Max sum (k=3): %d\n", maxSumFixed(arr1, 6, 3));  /* 9 */
 
    int arr2[] = {2, 3, 1, 2, 4, 3};
    printf("Min subarray sum>=7: length %d\n", smallestSubarray(arr2, 6, 7)); /* 2 — [4,3] */
 
    return 0;
}

Two pointers start at opposite ends of a sorted array and move toward each other. At each step, comparing their sum to the target tells you which pointer to move — eliminating one element from consideration per step. The result is O(n) instead of O(n²) brute force. Also applies to linked list cycle detection (Unit 05 — that was also two pointers: the slow and fast pointer).

#include <stdio.h>
 
/* PROBLEM 1: pair sum — find two elements that sum to target */
void pairSum(int arr[], int n, int target) {
    int left = 0, right = n - 1;  /* start from both ends */
 
    while (left < right) {
        int sum = arr[left] + arr[right];
 
        if (sum == target) {
            printf("Pair found: %d + %d = %d\n", arr[left], arr[right], target);
            left++; right--;
        } else if (sum < target) {
            left++;   /* sum too small — move left pointer right to increase sum */
        } else {
            right--;  /* sum too large — move right pointer left to decrease sum */
        }
    }
}
 
/* PROBLEM 2: container with most water
   Given heights[], find two lines that form the largest container */
int maxWater(int heights[], int n) {
    int left = 0, right = n - 1, maxArea = 0;
 
    while (left < right) {
        int h = heights[left] < heights[right] ? heights[left] : heights[right];
        int area = h * (right - left);
        if (area > maxArea) maxArea = area;
 
        /* move the shorter side — it is the limiting factor */
        if (heights[left] < heights[right]) left++;
        else right--;
    }
    return maxArea;
}
 
/* PROBLEM 3: remove duplicates from sorted array in-place */
int removeDuplicates(int arr[], int n) {
    if (n == 0) return 0;
    int slow = 0, fast;
 
    for (fast = 1; fast < n; fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];  /* copy unique element */
        }
        /* if duplicate — fast just moves on, slow stays */
    }
    return slow + 1;  /* new length */
}
 
int main() {
    int arr1[] = {1, 2, 3, 4, 6};  /* sorted */
    printf("Pair sum = 6:\n");
    pairSum(arr1, 5, 6);  /* 2+4, 1+5? no 5 not there. Actually 2+4=6 */
 
    int heights[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    printf("Max water: %d\n", maxWater(heights, 9));  /* 49 */
 
    int arr2[] = {1, 1, 2, 3, 3, 3, 4};
    int newLen = removeDuplicates(arr2, 7);
    printf("After dedup length: %d\n", newLen);  /* 4: [1,2,3,4] */
 
    return 0;
}

Every integer is stored as bits. Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) to work directly on these bits. The results are algorithms that look like magic but run in constant time O(1). Used in competitive programming, low-level systems, graphics, and cryptography.

#include <stdio.h>
 
/* ── ESSENTIAL BIT TRICKS ── */
 
/* 1. Check if a number is even or odd */
int isOdd(int n) { return n & 1; }
/* n & 1 checks the last bit: 1=odd, 0=even. Faster than n%2 */
 
/* 2. Check if number is a power of 2 */
int isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }
/* Powers of 2 have exactly one bit set: 4=100, n-1=011, AND=000 */
 
/* 3. Count set bits (Brian Kernighan's algorithm) */
int countBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);  /* clears the lowest set bit */
        count++;
    }
    return count;
}
 
/* 4. Get, set, clear, toggle the i-th bit */
int getBit(int n, int i)    { return (n >> i) & 1; }
int setBit(int n, int i)    { return n | (1 << i); }
int clearBit(int n, int i)  { return n & ~(1 << i); }
int toggleBit(int n, int i) { return n ^ (1 << i); }
 
/* 5. XOR trick: find the one number that appears once
   (all others appear exactly twice) */
int findUnique(int arr[], int n) {
    int result = 0, i;
    for (i = 0; i < n; i++) result ^= arr[i];
    /* x ^ x = 0 for all pairs, only the unique remains */
    return result;
}
 
/* 6. Swap two numbers without a temp variable */
void swapBits(int *a, int *b) {
    *a ^= *b;  /* a = a XOR b */
    *b ^= *a;  /* b = b XOR (a XOR b) = original a */
    *a ^= *b;  /* a = (a XOR b) XOR original a = original b */
}
 
/* 7. Multiply and divide by powers of 2 */
int multiplyBy2(int n)  { return n << 1; }
int divideBy2(int n)    { return n >> 1; }
int multiplyBy8(int n)  { return n << 3; }  /* 2^3 = 8 */
 
/* 8. Check if two integers have opposite signs */
int oppositeSigns(int a, int b) { return (a ^ b) < 0; }
 
int main() {
    printf("isOdd(7):        %d\n", isOdd(7));         /* 1 */
    printf("isOdd(8):        %d\n", isOdd(8));         /* 0 */
    printf("isPowerOf2(16):  %d\n", isPowerOf2(16));   /* 1 */
    printf("isPowerOf2(12):  %d\n", isPowerOf2(12));   /* 0 */
    printf("countBits(13):   %d\n", countBits(13));    /* 3 — 1101 has 3 set bits */
 
    printf("getBit(13, 2):   %d\n", getBit(13, 2));    /* 1 — 1101, bit 2 is 1 */
    printf("clearBit(13, 3): %d\n", clearBit(13, 3));  /* 5 — 1101 -> 0101 */
    printf("setBit(5, 3):    %d\n", setBit(5, 3));     /* 13 — 0101 -> 1101 */
 
    int arr[] = {4, 1, 2, 1, 2};
    printf("Unique element:  %d\n", findUnique(arr, 5)); /* 4 */
 
    int a = 10, b = 20;
    swapBits(&a, &b);
    printf("After swap: a=%d b=%d\n", a, b);  /* a=20 b=10 */
 
    return 0;
}

Zero to Advanced. Done.

From understanding what a variable is, to segment trees and bit manipulation — you have covered every topic that appears in technical interviews from campus placements all the way to FAANG India. That is 20 units, 135+ topics, and hundreds of problems. All in C. All from scratch.