敌情监控：多语言实现区间连续 K 个营地最小兵力之和

Python 实现

import sys

class SegmentTree:
    def __init__(self, n, k, arr):
        self.n = n
        self.k = k
        self.sum = [0] * (4 * n)
        self.minKSum = [float('inf')] * (4 * n)
        self.build(1, 1, n, arr)

    def build(self, node, l, r, arr):
        if l == r:
            self.sum[node] = arr[l]
            self.minKSum[node] = arr[l] if self.k == 1 else float('inf')
            return
        mid = (l + r) // 2
        self.build(node * 2, l, mid, arr)
        self.build(node * 2 + 1, mid + 1, r, arr)
        self.sum[node] = self.sum[node * 2] + self.sum[node * 2 + 1]
        # 合并子区间的 minKSum
        if r - l + 1 >= self.k:
            self.minKSum[node] = min(self.minKSum[node * 2], self.minKSum[node * 2 + 1])
            # 考虑跨越两个子区间的长度为 K 的子区间
            if mid - l + 1 >= self.k - (r - mid):
                left_start = max(l, mid - self.k + 2)
                for start in range(left_start, mid + 1):
                    end = start + self.k - 1
                    if end <= r:
                        self.minKSum[node] = min(self.minKSum[node], self._query_sum(start, end))
        else:
            self.minKSum[node] = float('inf')

    def update(self, node, l, r, idx, delta):
        if l == r:
            self.sum[node] += delta
            if self.k == 1:
                self.minKSum[node] = self.sum[node]
            return
        mid = (l + r) // 2
        if idx <= mid:
            self.update(node * 2, l, mid, idx, delta)
        else:
            self.update(node * 2 + 1, mid + 1, r, idx, delta)
        self.sum[node] = self.sum[node * 2] + self.sum[node * 2 + 1]
        # 重新计算 minKSum
        if r - l + 1 >= self.k:
            self.minKSum[node] = min(self.minKSum[node * 2], self.minKSum[node * 2 + 1])
            # 考虑跨越两个子区间的长度为 K 的子区间
            if mid - l + 1 >= self.k - (r - mid):
                left_start = max(l, mid - self.k + 2)
                for start in range(left_start, mid + 1):
                    end = start + self.k - 1
                    if end <= r:
                        self.minKSum[node] = min(self.minKSum[node], self._query_sum(start, end))
        else:
            self.minKSum[node] = float('inf')

    def query_min_k_sum(self, node, l, r, ql, qr):
        if ql > qr or r - l + 1 < self.k:
            return float('inf')
        if ql <= l and r <= qr:
            if r - l + 1 >= self.k:
                return self.minKSum[node]
            return float('inf')
        mid = (l + r) // 2
        result = float('inf')
        if ql <= mid:
            result = min(result, self.query_min_k_sum(node * 2, l, mid, ql, min(qr, mid)))
        if qr > mid:
            result = min(result, self.query_min_k_sum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr))
        # 考虑跨越两个子区间的长度为 K 的子区间
        if ql <= mid and qr > mid:
            left_start = max(ql, mid - self.k + 2)
            right_end = min(qr, mid + self.k - 1)
            for start in range(left_start, mid + 1):
                end = start + self.k - 1
                if end <= qr and end >= ql + self.k - 1:
                    result = min(result, self._query_sum(start, end))
        return result

    def _query_sum(self, l, r):
        return self._query_sum_helper(1, 1, self.n, l, r)

    def _query_sum_helper(self, node, l, r, ql, qr):
        if ql > qr: return 0
        if ql <= l and r <= qr: return self.sum[node]
        mid = (l + r) // 2
        result = 0
        if ql <= mid: result += self._query_sum_helper(node * 2, l, mid, ql, min(qr, mid))
        if qr > mid: result += self._query_sum_helper(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr)
        return result

def main():
    data = sys.stdin.read().strip().split()
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    arr = [0] * (N + 1)
    for i in range(1, N + 1):
        arr[i] = int(data[idx]); idx += 1
    seg_tree = SegmentTree(N, K, arr)
    results = []
    for _ in range(L):
        cmd = data[idx]; idx += 1
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        if cmd == "Add":
            seg_tree.update(1, 1, N, x, y)
        elif cmd == "Sub":
            seg_tree.update(1, 1, N, x, -y)
        elif cmd == "Query":
            # 查询区间 [x, y] 中长度为 K 的最小和
            result = seg_tree.query_min_k_sum(1, 1, N, x, y - K + 1)
            results.append(str(result))
    print("\n".join(results))

if __name__ == "__main__":
    main()

C++ 实现

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

class SegmentTree {
private:
    int n, k;
    vector<int> sum;
    vector<int> minKSum;

    void build(int node, int l, int r, vector<int>& arr) {
        if (l == r) {
            sum[node] = arr[l];
            minKSum[node] = (k == 1) ? arr[l] : INT_MAX;
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, arr);
        build(node * 2 + 1, mid + 1, r, arr);
        sum[node] = sum[node * 2] + sum[node * 2 + 1];
        if (r - l + 1 >= k) {
            minKSum[node] = min(minKSum[node * 2], minKSum[node * 2 + 1]);
            if (mid - l + 1 >= k - (r - mid)) {
                int leftStart = max(l, mid - k + 2);
                for (int start = leftStart; start <= mid; start++) {
                    int end = start + k - 1;
                    if (end <= r) {
                        minKSum[node] = min(minKSum[node], querySum(start, end));
                    }
                }
            }
        } else {
            minKSum[node] = INT_MAX;
        }
    }

    int querySum(int l, int r) {
        return querySum(1, 1, n, l, r);
    }

    int querySum(int node, int l, int r, int ql, int qr) {
        if (ql > qr) return 0;
        if (ql <= l && r <= qr) return sum[node];
        int mid = (l + r) / 2;
        int result = 0;
        if (ql <= mid) result += querySum(node * 2, l, mid, ql, min(qr, mid));
        if (qr > mid) result += querySum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr);
        return result;
    }

public:
    SegmentTree(int n, int k, vector<int>& arr) : n(n), k(k) {
        sum.resize(4 * n);
        minKSum.resize(4 * n, INT_MAX);
        build(1, 1, n, arr);
    }

    void update(int node, int l, int r, int idx, int delta) {
        if (l == r) {
            sum[node] += delta;
            if (k == 1) {
                minKSum[node] = sum[node];
            }
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) {
            update(node * 2, l, mid, idx, delta);
        } else {
            update(node * 2 + 1, mid + 1, r, idx, delta);
        }
        sum[node] = sum[node * 2] + sum[node * 2 + 1];
        if (r - l + 1 >= k) {
            minKSum[node] = min(minKSum[node * 2], minKSum[node * 2 + 1]);
            if (mid - l + 1 >= k - (r - mid)) {
                int leftStart = max(l, mid - k + 2);
                for (int start = leftStart; start <= mid; start++) {
                    int end = start + k - 1;
                    if (end <= r) {
                        minKSum[node] = min(minKSum[node], querySum(start, end));
                    }
                }
            }
        } else {
            minKSum[node] = INT_MAX;
        }
    }

    int queryMinKSum(int node, int l, int r, int ql, int qr) {
        if (ql > qr || r - l + 1 < k) {
            return INT_MAX;
        }
        if (ql <= l && r <= qr) {
            if (r - l + 1 >= k) {
                return minKSum[node];
            }
            return INT_MAX;
        }
        int mid = (l + r) / 2;
        int result = INT_MAX;
        if (ql <= mid) {
            result = min(result, queryMinKSum(node * 2, l, mid, ql, min(qr, mid)));
        }
        if (qr > mid) {
            result = min(result, queryMinKSum(node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr));
        }
        if (ql <= mid && qr > mid) {
            int leftStart = max(ql, mid - k + 2);
            int rightEnd = min(qr, mid + k - 1);
            for (int start = leftStart; start <= mid; start++) {
                int end = start + k - 1;
                if (end <= qr && end >= ql + k - 1) {
                    result = min(result, querySum(start, end));
                }
            }
        }
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K, L;
    cin >> N >> K >> L;
    vector<int> arr(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    SegmentTree segTree(N, K, arr);
    for (int i = 0; i < L; i++) {
        string cmd;
        int x, y;
        cin >> cmd >> x >> y;
        if (cmd == "Add") {
            segTree.update(1, 1, N, x, y);
        } else if (cmd == "Sub") {
            segTree.update(1, 1, N, x, -y);
        } else if (cmd == "Query") {
            int result = segTree.queryMinKSum(1, 1, N, x, y - K + 1);
            cout << result << "\n";
        }
    }
    return 0;
}

JavaScript 实现

const readline = require('readline');

class SegmentTree {
    constructor(n, k, arr) {
        this.n = n;
        this.k = k;
        this.sum = new Array(4 * n).fill(0);
        this.minKSum = new Array(4 * n).fill(Infinity);
        this.build(1, 1, n, arr);
    }

    build(node, l, r, arr) {
        if (l === r) {
            this.sum[node] = arr[l];
            this.minKSum[node] = (this.k === 1) ? arr[l] : Infinity;
            return;
        }
        const mid = Math.floor((l + r) / 2);
        this.build(node * 2, l, mid, arr);
        this.build(node * 2 + 1, mid + 1, r, arr);
        this.sum[node] = this.sum[node * 2] + this.sum[node * 2 + 1];
        if (r - l + 1 >= this.k) {
            this.minKSum[node] = Math.min(this.minKSum[node * 2], this.minKSum[node * 2 + 1]);
            if (mid - l + 1 >= this.k - (r - mid)) {
                const leftStart = Math.max(l, mid - this.k + 2);
                for (let start = leftStart; start <= mid; start++) {
                    const end = start + this.k - 1;
                    if (end <= r) {
                        this.minKSum[node] = Math.min(this.minKSum[node], this._querySum(start, end));
                    }
                }
            }
        } else {
            this.minKSum[node] = Infinity;
        }
    }

    update(node, l, r, idx, delta) {
        if (l === r) {
            this.sum[node] += delta;
            if (this.k === 1) {
                this.minKSum[node] = this.sum[node];
            }
            return;
        }
        const mid = Math.floor((l + r) / 2);
        if (idx <= mid) {
            this.update(node * 2, l, mid, idx, delta);
        } else {
            this.update(node * 2 + 1, mid + 1, r, idx, delta);
        }
        this.sum[node] = this.sum[node * 2] + this.sum[node * 2 + 1];
        if (r - l + 1 >= this.k) {
            this.minKSum[node] = Math.min(this.minKSum[node * 2], this.minKSum[node * 2 + 1]);
            if (mid - l + 1 >= this.k - (r - mid)) {
                const leftStart = Math.max(l, mid - this.k + 2);
                for (let start = leftStart; start <= mid; start++) {
                    const end = start + this.k - 1;
                    if (end <= r) {
                        this.minKSum[node] = Math.min(this.minKSum[node], this._querySum(start, end));
                    }
                }
            }
        } else {
            this.minKSum[node] = Infinity;
        }
    }

    queryMinKSum(node, l, r, ql, qr) {
        if (ql > qr || r - l + 1 < this.k) {
            return Infinity;
        }
        if (ql <= l && r <= qr) {
            if (r - l + 1 >= this.k) {
                return this.minKSum[node];
            }
            return Infinity;
        }
        const mid = Math.floor((l + r) / 2);
        let result = Infinity;
        if (ql <= mid) {
            result = Math.min(result, this.queryMinKSum(node * 2, l, mid, ql, Math.min(qr, mid)));
        }
        if (qr > mid) {
            result = Math.min(result, this.queryMinKSum(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr));
        }
        if (ql <= mid && qr > mid) {
            const leftStart = Math.max(ql, mid - this.k + 2);
            const rightEnd = Math.min(qr, mid + this.k - 1);
            for (let start = leftStart; start <= mid; start++) {
                const end = start + this.k - 1;
                if (end <= qr && end >= ql + this.k - 1) {
                    result = Math.min(result, this._querySum(start, end));
                }
            }
        }
        return result;
    }

    _querySum(l, r) {
        return this._querySumHelper(1, 1, this.n, l, r);
    }

    _querySumHelper(node, l, r, ql, qr) {
        if (ql > qr) return 0;
        if (ql <= l && r <= qr) return this.sum[node];
        const mid = Math.floor((l + r) / 2);
        let result = 0;
        if (ql <= mid) result += this._querySumHelper(node * 2, l, mid, ql, Math.min(qr, mid));
        if (qr > mid) result += this._querySumHelper(node * 2 + 1, mid + 1, r, Math.max(ql, mid + 1), qr);
        return result;
    }
}

async function main() {
    const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
    const lines = [];
    for await (const line of rl) {
        lines.push(line);
    }
    const firstLine = lines[0].split(' ').map(Number);
    const N = firstLine[0];
    const K = firstLine[1];
    const L = firstLine[2];
    const arr = [0];
    lines[1].split(' ').forEach(val => arr.push(Number(val)));
    const segTree = new SegmentTree(N, K, arr);
    const results = [];
    for (let i = 0; i < L; i++) {
        const [cmd, xStr, yStr] = lines[2 + i].split(' ');
        const x = parseInt(xStr);
        const y = parseInt(yStr);
        if (cmd === "Add") {
            segTree.update(1, 1, N, x, y);
        } else if (cmd === "Sub") {
            segTree.update(1, 1, N, x, -y);
        } else if (cmd === "Query") {
            const result = segTree.queryMinKSum(1, 1, N, x, y - K + 1);
            results.push(result.toString());
        }
    }
    console.log(results.join('\n'));
    rl.close();
}

main().catch(console.error);

C 实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
    int n, k;
    int* sum;
    int* minKSum;
} SegmentTree;

void build(SegmentTree* st, int node, int l, int r, int* arr) {
    if (l == r) {
        st->sum[node] = arr[l];
        st->minKSum[node] = (st->k == 1) ? arr[l] : INT_MAX;
        return;
    }
    int mid = (l + r) / 2;
    build(st, node * 2, l, mid, arr);
    build(st, node * 2 + 1, mid + 1, r, arr);
    st->sum[node] = st->sum[node * 2] + st->sum[node * 2 + 1];
    if (r - l + 1 >= st->k) {
        st->minKSum[node] = min(st->minKSum[node * 2], st->minKSum[node * 2 + 1]);
        if (mid - l + 1 >= st->k - (r - mid)) {
            int leftStart = max(l, mid - st->k + 2);
            for (int start = leftStart; start <= mid; start++) {
                int end = start + st->k - 1;
                if (end <= r) {
                    // 计算区间和
                    int sum = 0;
                    for (int i = start; i <= end; i++) {
                        sum += arr[i];
                    }
                    st->minKSum[node] = min(st->minKSum[node], sum);
                }
            }
        }
    } else {
        st->minKSum[node] = INT_MAX;
    }
}

SegmentTree* createSegmentTree(int n, int k, int* arr) {
    SegmentTree* st = (SegmentTree*)malloc(sizeof(SegmentTree));
    st->n = n;
    st->k = k;
    st->sum = (int*)malloc(4 * n * sizeof(int));
    st->minKSum = (int*)malloc(4 * n * sizeof(int));
    // 初始化
    for (int i = 0; i < 4 * n; i++) {
        st->sum[i] = 0;
        st->minKSum[i] = INT_MAX;
    }
    build(st, 1, 1, n, arr);
    return st;
}

int querySum(SegmentTree* st, int node, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return st->sum[node];
    int mid = (l + r) / 2;
    int result = 0;
    if (ql <= mid) result += querySum(st, node * 2, l, mid, ql, min(qr, mid));
    if (qr > mid) result += querySum(st, node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr);
    return result;
}

void update(SegmentTree* st, int node, int l, int r, int idx, int delta, int* arr) {
    if (l == r) {
        st->sum[node] += delta;
        arr[l] += delta;
        if (st->k == 1) {
            st->minKSum[node] = st->sum[node];
        }
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) {
        update(st, node * 2, l, mid, idx, delta, arr);
    } else {
        update(st, node * 2 + 1, mid + 1, r, idx, delta, arr);
    }
    st->sum[node] = st->sum[node * 2] + st->sum[node * 2 + 1];
    if (r - l + 1 >= st->k) {
        st->minKSum[node] = min(st->minKSum[node * 2], st->minKSum[node * 2 + 1]);
        if (mid - l + 1 >= st->k - (r - mid)) {
            int leftStart = max(l, mid - st->k + 2);
            for (int start = leftStart; start <= mid; start++) {
                int end = start + st->k - 1;
                if (end <= r) {
                    int sum = 0;
                    for (int i = start; i <= end; i++) {
                        sum += arr[i];
                    }
                    st->minKSum[node] = min(st->minKSum[node], sum);
                }
            }
        }
    } else {
        st->minKSum[node] = INT_MAX;
    }
}

int queryMinKSum(SegmentTree* st, int node, int l, int r, int ql, int qr, int* arr) {
    if (ql > qr || r - l + 1 < st->k) {
        return INT_MAX;
    }
    if (ql <= l && r <= qr) {
        if (r - l + 1 >= st->k) {
            return st->minKSum[node];
        }
        return INT_MAX;
    }
    int mid = (l + r) / 2;
    int result = INT_MAX;
    if (ql <= mid) {
        result = min(result, queryMinKSum(st, node * 2, l, mid, ql, min(qr, mid), arr));
    }
    if (qr > mid) {
        result = min(result, queryMinKSum(st, node * 2 + 1, mid + 1, r, max(ql, mid + 1), qr, arr));
    }
    if (ql <= mid && qr > mid) {
        int leftStart = max(ql, mid - st->k + 2);
        int rightEnd = min(qr, mid + st->k - 1);
        for (int start = leftStart; start <= mid; start++) {
            int end = start + st->k - 1;
            if (end <= qr && end >= ql + st->k - 1) {
                int sum = 0;
                for (int i = start; i <= end; i++) {
                    sum += arr[i];
                }
                result = min(result, sum);
            }
        }
    }
    return result;
}

void freeSegmentTree(SegmentTree* st) {
    free(st->sum);
    free(st->minKSum);
    free(st);
}

int main() {
    int N, K, L;
    scanf("%d %d %d", &N, &K, &L);
    int* arr = (int*)malloc((N + 1) * sizeof(int));
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
    SegmentTree* st = createSegmentTree(N, K, arr);
    for (int i = 0; i < L; i++) {
        char cmd[10];
        int x, y;
        scanf("%s %d %d", cmd, &x, &y);
        if (strcmp(cmd, "Add") == 0) {
            update(st, 1, 1, N, x, y, arr);
        } else if (strcmp(cmd, "Sub") == 0) {
            update(st, 1, 1, N, x, -y, arr);
        } else if (strcmp(cmd, "Query") == 0) {
            int result = queryMinKSum(st, 1, 1, N, x, y - K + 1, arr);
            printf("%d\n", result);
        }
    }
    free(arr);
    freeSegmentTree(st);
    return 0;
}