트 리 배열 모드 (구간 업데이트, 구간 조회, 단일 업데이트, 단일 조회)

1507 단어 데이터 구조
#include 
using namespace std;

#define ll long long
#define mem(a, b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define DBG printf("this is a input
") //D[i] ll sum1[500005]; //D[1]+D[2]+D[3]+...+D[i] ll sum2[500005]; //D[1]+2*D[2]+3*D[3]+...+n*D[n]; int n , m, num[500005]; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int lowbit(int x) { return x & (-x); } void update(int x , int k)// { int xi = x; while(x <= n) { // k sum1[x] += k; sum2[x] += k*(xi-1); x += lowbit(x); } } ll get_sum (int x) //1-x { ll sum= 0; int xi = x; while(x > 0) { sum += xi * sum1[x] - sum2[x]; x -= lowbit(x); } return sum; } int main(void) { mem(num,0); mem(sum1,0); mem(sum2,0); ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> num[i]; update(i, num[i] - num[i - 1]); // } while(m --) { int z; cin>>z; if(z == 1) { int l , r , k; cin>>l>>r>>k; // update(l,k); update(r+1,0-k); } else { int k; cin>>k; // cout<

좋은 웹페이지 즐겨찾기