electicode
HomeCoursesResourcesProblemsNational OlympiadContestsLeaderboard
...
Problems/Boring Data Structure/Editorial

Editorial: Boring Data Structure

Notation & Definitions

  • N: Size of the array
  • Q: Number of operations
  • A[i]: Value at position i in the array
  • BIT (Fenwick Tree): Binary Indexed Tree for efficient prefix sum operations
  • Difference Array: Array where diff[i] = A[i] - A[i-1], allowing efficient range updates
  • Segment Tree: Tree data structure for range queries and updates
  • Lazy Propagation: Technique to defer updates until necessary

Subtask 1: Only Operations Type 1, 2 (7 points)

Editorial

When we only have queries and swaps (no range updates), the problem becomes trivial. We can maintain a simple array and perform operations directly:

  • Type 1 Query: Return A[i] in O(1)
  • Type 2 Swap: Swap A[i] and A[j] in O(1)

This approach is straightforward since we don't need to handle range updates.

Complexity

  • Time Complexity: O(Q)
  • Space Complexity: O(N)

Subtask 2: Only Operations Type 1, 3 (29 points)

Editorial

This subtask requires efficient range updates and point queries - a classic problem solved with the difference array technique:

Maintain a difference array in a Fenwick Tree where we store diff[i] = A[i] - A[i-1].

Key Insight: If diff[i] = A[i] - A[i-1], then A[i] = diff[1] + diff[2] + ... + diff[i] (prefix sum).

Operations:

  • Type 1 Query: Compute prefix sum up to position i: O(log N)
  • Type 3 Range Update [l, r] by x:
    • Add x at position l: diff[l] += x
    • Subtract x at position r+1: diff[r+1] -= x
    • This increases all A[l..r] by x while keeping A[r+1..N] unchanged
    • Time: O(log N)

Complexity

  • Time Complexity: O(Q log N)
  • Space Complexity: O(N)

Subtask 3: N, Q ≤ 2000 (17 points)

Editorial

With small constraints, a naive approach works perfectly:

  • Type 1 Query: Return A[i] in O(1)
  • Type 2 Swap: Swap A[i] and A[j] in O(1)
  • Type 3 Range Update: Iterate through [l, r] and add x to each element in O(N)

This brute-force solution is acceptable since Q·N ≤ 4·10^6.

Complexity

  • Time Complexity: O(Q·N)
  • Space Complexity: O(N)

Subtask 4: Full Solution (47 points)

Editorial

The full problem requires handling both swaps and range updates efficiently. The challenge is combining the difference array technique with swaps.

Approach: Fenwick Tree with Difference Array

We maintain a BIT storing the difference array: diff[i] = A[i] - A[i-1].

Operations:

  1. Type 1 (Query position i):

    • Compute A[i] = prefix_sum(i) = sum of diff[1..i]
    • Time: O(log N)

  2. Type 3 (Range update [l, r] by x):

    • Add x at position l
    • Subtract x at position r+1
    • Time: O(log N)

  3. Type 2 (Swap positions l and r) - The Key Insight:

    • Get current values: val_l = get(l), val_r = get(r)
    • Compute difference: d = val_l - val_r
    • To swap, we need val_l to become val_r and val_r to become val_l
    • Update differences:
      • diff[l] -= d (decrease A[l] by d)
      • diff[l+1] += d (cancel effect after position l)
      • diff[r] += d (increase A[r] by d)
      • diff[r+1] -= d (cancel effect after position r)
    • Time: O(log N)

Why this works for swaps: By using the difference array, we can modify a single position without affecting others by updating at position i and canceling at position i+1.

Complexity

  • Time Complexity: O(Q log N)
  • Space Complexity: O(N)
← Back to Problem
#include <bits/stdc++.h>

using namespace std;

class FenwickTree {
private:
    vector<long long> tree;
    int size;
    
public:
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    
    // Add delta to position pos
    void update(int pos, long long delta) {
        for (; pos <= size; pos += pos & (-pos)) {
            tree[pos] += delta;
        }
    }
    
    // Get prefix sum from 1 to pos
    long long query(int pos) {
        long long sum = 0;
        for (; pos > 0; pos -= pos & (-pos)) {
            sum += tree[pos];
        }
        return sum;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    FenwickTree bit(n);
    
    // Initialize difference array: diff[i] = A[i] - A[i-1]
    long long previous = 0;
    for (int i = 1; i <= n; i++) {
        long long current;
        cin >> current;
        bit.update(i, current - previous);
        previous = current;
    }
    
    // Process queries
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        
        if (type == 1) {
            // Query: get value at position pos
            int pos;
            cin >> pos;
            cout << bit.query(pos) << '\n';
            
        } else if (type == 2) {
            // Swap: exchange values at positions left and right
            int left, right;
            cin >> left >> right;
            
            long long value_left = bit.query(left);
            long long value_right = bit.query(right);
            long long difference = value_left - value_right;
            
            // Update differences to swap values
            bit.update(left, -difference);
            bit.update(left + 1, difference);
            bit.update(right, difference);
            bit.update(right + 1, -difference);
            
        } else {
            // Range update: add x to all elements in [left, right]
            int left, right;
            long long x;
            cin >> left >> right >> x;
            
            bit.update(left, x);
            bit.update(right + 1, -x);
        }
    }
    
    return 0;
}