为什么

P1001 A+B Problem

Spir1t @ 2023-07-11 11:16:28

为什么40分

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    vector<int> arr;
    vector<int> tree;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            build(leftChild, start, mid);
            build(rightChild, mid + 1, end);

            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            if (idx <= mid) {
                update(leftChild, start, mid, idx, val);
            } else {
                update(rightChild, mid + 1, end, idx, val);
            }

            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }

    int query(int node, int start, int end, int left, int right) {
        if (start > right || end < left) {
            return 0;
        } else if (start >= left && end <= right) {
            return tree[node];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            int sumLeft = query(leftChild, start, mid, left, right);
            int sumRight = query(rightChild, mid + 1, end, left, right);

            return sumLeft + sumRight;
        }
    }

public:
    SegmentTree(vector<int>& arr) {
        this->arr = arr;
        this->tree.resize(4 * arr.size());
        build(1, 0, arr.size() - 1);
    }

    void update(int idx, int val) {
        update(1, 0, arr.size() - 1, idx, val);
    }

    int query(int left, int right) {
        return query(1, 0, arr.size() - 1, left, right);
    }
};

int main() {
    int a, b;
    cin >> a >> b;

    vector<int> arr(max(a, b), 0);
    SegmentTree tree(arr);

    tree.update(a - 1, a);
    tree.update(b - 1, b);

    int result = tree.query(0, arr.size() - 1);
    cout << result << endl;

    return 0;
}

by Henry2012 @ 2023-07-11 11:19:38

线段树写A+B……

by Usada_Pekora @ 2023-07-11 11:23:35

@Sky_lzr03 因为有负数，而且你的复杂度 O(\max(a,b)).

by Spir1t @ 2023-07-11 12:49:29

@Usada_Pekora

ok，懂力

by HHYQ_07 @ 2023-08-04 15:34:07

线段树代码如下：


#include<bits/stdc++.h>
using namespace std;
const int N=5;
int a[N],n=2;
struct node
{
    int l,r,delta;
}t[N*4]; 
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
        t[p].delta=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].delta=t[p*2].delta+t[p*2+1].delta;
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r)return t[p].delta;
    int mid=(t[p].l+t[p].r)/2,ans=0;
    if(l<=mid)ans+=query(p*2,l,r);
    if(mid<r)ans+=query(p*2+1,l,r);
    return ans;
}
int main()
{
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    cout<<query(1,1,n);
    return 0;
}

by Spir1t @ 2023-08-09 16:33:36

@hhyz100413

谢谢dalao

by tkm2013 @ 2023-08-10 11:12:56

大哥串台了

|